Motivering: Med tanke på protein-protein interaktion (PPI) nätverk av ett par arter, en parvis global anpassning motsvarar en en-till-ett kartläggning mellan sina proteiner. Baserat på antagandet att en sådan kartläggning ger par av funktionellt ortologa proteiner korrekt, resultaten av anpassningen kan sedan användas i komparativa system biologiska problem såsom funktionsförutsägelse/verifiering eller konstruktion av evolutionära relationer. Resultat: Vi visar att problemet är NP-hård även för det fall där par av nätverk är helt enkelt vägar. Vi ger sedan en polynomisk tidsheuristisk algoritm, SPINAL, som består av två huvudfaser. I den första grovkorniga anpassningsfasen, konstruerar vi alla parvis initiala likhetspoäng baserat på parvis lokala grannmatchningar. Med hjälp av de producerade likhetspoängen producerar den finkorniga anpassningsfasen den slutliga en-till-en-kartläggningen genom att iterativt odla en lokalt förbättrad lösningsdelmängd. Båda faserna utnyttjar byggandet av tvåpartsgrafer i grannskapet och bidragsgivarna som en gemensam primitiv. Vi bedömer prestandan hos vår algoritm på PPI nätverk av jäst, fluga, människa och mask. Vi visar att baserat på de noggrannhetsmått som används i relevant arbete överträffar vår metod toppmoderna algoritmer. Dessutom lider vår algoritm inte av skalbarhetsproblem, eftersom sådana korrekta resultat uppnås i rimliga drifttider jämfört med referensalgoritmerna. Tillgänglighet: Kompletterande dokument, öppen källkod, användbara skript, alla experimentella data och resultaten är fritt tillgängliga på
SPINAL-algoritmen REF ökar iterativt anpassningen baserat på apriori beräknas nod likhet poäng.
SPINAL: Scalable Protein Interaction Network Alignment
{'venue': 'Bioinformatics', 'journal': 'Bioinformatics', 'mag_field_of_study': ['Medicine', 'Computer Science']}