Motivering: Global många-till-många anpassning av biologiska nätverk har varit ett centralt problem i jämförande biologiska nätverksstudier. Med tanke på en uppsättning biologiska interaktionsnätverk är det informella målet att gruppera samman relaterade noder. När det gäller protein-protein-interaktioner (PPI) nätverk sådana grupper förväntas bilda kluster av funktionellt ortologa proteiner. Uppbyggnad av sådana kluster för nätverk från olika arter kan visa sig vara ganska användbart för att bestämma evolutionära relationer, för att förutsäga funktioner proteiner med okända funktioner, och för att verifiera dem med uppskattade funktioner. Resultat: Ett centralt informellt mål i uppbyggnaden av kluster av ortologa proteiner är att garantera att varje kluster består av medlemmar med hög homolog likhet, vanligen bestäms via sekvenslikheter, och att interaktioner mellan de proteiner som är involverade i samma kluster bevaras över ingångsnätverken. Vi ger en formell definition av den globala många-till-många anpassningen av flera PPI-nätverk som fångar detta informella mål. Vi visar den beräknade intractabilityen av den föreslagna definitionen. Vi tillhandahåller en heuristisk metod baserad på ryggradsextraktion och sammanfogningsstrategi (BEAMS) för problemet. Vi visar slutligen, genom experiment baserade på tester av biologisk signifikans, att den föreslagna BEAMS-algoritmen fungerar bättre än den senaste tekniken. Dessutom är BEAMS-algoritmens beräkningsbörda i fråga om exekveringshastighet och minneskrav mer rimlig än de konkurrerande algoritmerna. Tillgänglighet: Kompletterande material inklusive kodimplementeringar i LEDA C++, experimentella data och resultaten finns tillgängliga på
Alken et al., gav en heuristisk metod baserad på ryggrad utvinning och sammanslagning strategi (BEAMS) för den globala många-till-många anpassning av flera PPI-nätverk REF.
BEAMS: Backbone Extraction and Merge Strategy for the Global Many-to-Many Alignment of Multiple PPI Networks
{'venue': 'Bioinformatics', 'journal': 'Bioinformatics', 'mag_field_of_study': ['Computer Science', 'Medicine']}