Bakgrund: Förutom komponentbaserade jämförande metoder ger nätverksanpassningar möjlighet att studera bevarad nätverkstopologi såsom gemensamma vägar och mer komplexa nätverksmotiv. Men till skillnad från klassisk sekvensanpassning blir jämförelsen av nätverk mer utmanande, eftersom de mest meningsfulla antagandena omedelbart leder till NPhard-problem. De flesta tidigare algoritmiska arbeten på nätverksanpassningar är heuristiska till sin natur. Vi introducerar graf-baserad maximal strukturell matchning formulering för pairwise global nätverksanpassning. Vi relaterar formuleringen till tidigare arbete och bevisar NP-hårdheten i problemet. Baserat på den nya formuleringen bygger vi på de senaste resultaten i beräkningsstrukturbiologi och presenterar en ny Lagrangian relaxation strategi som, i kombination med en gren-och-bunden metod, beräknar bevisligen optimala nätverksanpassningar. Enbart den Lagrangianska algoritmen är en kraftfull heuristisk metod, som producerar lösningar som ofta är nästan optimala och -till skillnad från dem som beräknas av ren heuristik - kommer med en kvalitetsgaranti. Beräkningsförsök på anpassning av protein-protein interaktionsnätverk och på klassificeringen av metabola subnätverk visar att den nya metoden är någorlunda snabb och har fördelar jämfört med ren heuristik. Vårt programvaruverktyg är fritt tillgängligt som en del av LISA-biblioteket. I systembiologin modelleras ofta komplexa biologiska system som nätverk. Exempel är protein-proteininteraktion (PPI), metaboliska, genreglerande och signaltransduktionsnätverk. Den ökande kvaliteten och mängden tillgängliga data skapar behovet av automatiserade analysmetoder för att bättre förstå cellprocesser, nätverksorganisation, evolutionära förändringar och sjukdomsmekanismer [1, 2]. Baserat på antagandet att evolutionärt bevarande innebär funktionell betydelse, jämförande metoder kan bidra till att förbättra noggrannheten hos data, elucidate proteinvägar och komplex, generera, undersöka och validera hypoteser om de underliggande nätverken, och överföra funktionella annoteringar. Förutom komponentbaserade jämförande metoder ger nätverksanpassningar möjlighet att studera bevarad nättopologi såsom gemensamma vägar och mer komplexa nätverksmotiv. Men, till skillnad från i klassisk sekvens anpassning, jämförelsen av nätverk blir
Klau formulerar problemet baserat på maximal vikt spår och föreslår en lagrangian avslappning approach REF.
A new graph-based method for pairwise global network alignment
{'venue': 'BMC Bioinformatics', 'journal': 'BMC Bioinformatics', 'mag_field_of_study': ['Computer Science', 'Medicine']}