Bakgrund: Proteininteraktioner är viktiga komponenter i alla cellulära processer. Nyligen har metoder med hög genomströmning utvecklats för att få en global beskrivning av interaktionen (hela nätverket av proteininteraktioner för en viss organism). Under 2002 uppskattades jästinteraktionen innehålla upp till 80.000 potentiella interaktioner. Denna uppskattning baseras på integration av datamängder som erhållits med olika metoder (masspektrometri, tvåhybridmetoder, genetiska studier). Högt genomflödesmetoder är dock kända för att ge en icke-försumbar frekvens av falska positiva, och att missa en bråkdel av befintliga interaktioner. Interaktionen kan representeras som en graf där noderna motsvarar proteiner och kanter med parvisa interaktioner. Under de senaste åren har klustermetoder utvecklats och tillämpats för att extrahera relevanta moduler från sådana grafer. Dessa algoritmer kräver specifikation av parametrar som drastiskt kan påverka resultaten. I detta dokument presenterar vi en jämförande bedömning av fyra algoritmer: Markov Clustering (MCL), Restrikted Neighborhood Search Clustering (RNSC), Super Paramagnetic Clustering (SPC), och Molecular Complex Detection (MCODE). En testgraf byggdes på grundval av 220 komplex som kommenterades i MIPS-databasen. För att utvärdera robustheten till falska positiva och falska negativa, härledde vi 41 förändrade grafer genom att slumpmässigt ta bort kanter från eller lägga till kanter till testgrafen i olika proportioner. Varje klusteralgoritm tillämpades på dessa grafer med olika parameterinställningar, och klustren jämfördes med de kommenterade komplexen. Vi analyserade algoritmernas känslighet för parametrarna och bestämde deras optimala parametervärden. Vi utvärderade också deras robusthet till ändringar av testgrafen. Vi tillämpade sedan de fyra algoritmerna på sex grafer som erhållits från experiment med hög genomströmning och jämförde de resulterande klungorna med de kommenterade komplexen. Slutsats: Denna analys visar att MCL är anmärkningsvärt robust för att grafen förändringar. I testerna av robusthet är RNSC mer känslig för kantradering men mindre känslig för användning av suboptimala parametervärden. De andra två algoritmerna är klart svagare under de flesta förhållanden. Analysen av data med hög genomströmning stöder MCL:s överlägsenhet för utvinning av komplex från interaktionsnätverk.
Brohee och Heldan REF gjorde en jämförande bedömning för protein-protein interaktionsnätverk av fyra klusteralgoritmer: Markov clustring (MCL), begränsad områdessökning kluster (RNSC), superparamagnetisk klusterbildning (SPC) och molekylär komplex detektion (MCODE).
Evaluation of clustering algorithms for protein-protein interaction networks
{'venue': 'BMC Bioinformatics', 'journal': 'BMC Bioinformatics', 'mag_field_of_study': ['Computer Science', 'Medicine']}