Intuitivt bör en subgraf som representerar ett proteinkomplex uppfylla två enkla strukturella egenskaper: den bör innehålla många tillförlitliga interaktioner mellan dess subenheter, och den bör vara väl separerad från resten av nätverket. Vi formaliserade dessa två egenskaper i ett kvalitetsmått som vi kallade sammanhållning och utvecklade en algoritm som upptäcker eventuellt överlappande proteinkomplex från viktade nätverk, med hjälp av sammanhållning för att vägleda sökningen. Vår algoritm består av tre stora steg (Online Methods). Först, med början från ett enda frö vertex, ett girigt förfarande lägger till eller tar bort hörn för att hitta grupper med hög sammanhållning. Tillväxtprocessen upprepas från olika frön för att bilda flera, möjligen överlappande grupper. Även om vissa överlappningar sannolikt har biologisk betydelse bör grupper som överlappar varandra i mycket hög grad jämfört med deras storlek sannolikt slås samman. I det andra steget kvantifierar vi graden av överlappning mellan varje grupppar och slår samman de grupper för vilka överlappningspoäng 4 ligger över ett angivet tröskelvärde. I det tredje steget kastar vi bort komplexa kandidater som innehåller mindre än tre proteiner eller vars densitet ligger under en given tröskel. Observera att vår metod potentiellt kan användas för att känna igen inte bara partiella överlappningar utan även fall där ett komplex är helt inneslutet i ett annat komplex. Vi testade ClusterONE på fem storskaliga jäst PPI dataset (kompletterande data 1), fyra viktade 6-8 och en oviktad 9, och jämförde ClusterONE till en representativ uppsättning av andra metoder: Markov kluster (MCL) 1, molekylär komplex detektion (MCODE) 4, affinitet förökning 10, begränsad område söka kluster algoritm (RNSC) 2, CFinder 11, klusterering baserad på maximal cliques (CMC) 5 och upprepade slumpmässiga promenader (RRW) 12 (kompletterande diskussion). Vi jämförde förutsagda komplex till två referenskomplex uppsättningar: den första härledd från MIPS katalog av proteinkomplex 13 och den andra från Gene Ontologybaserade komplexa anteckningar i SGD (kompletterande data 2). Vi bedömde kvaliteten på de förutsagda komplexen med tre poäng: andelen proteinkomplex som matchas med minst ett förutsagt komplex; den geometriska noggrannheten mäter 14; och den maximala matchningsförhållandet, en poäng som vi föreslår här baserat på en maximal en-till-en kartläggning mellan förutsagda och referenskomplex (Online Methods). Vi presenterar de tre kvalitetspoäng som erhållits med hjälp av MIPS referensuppsättning (Fig. 1a) ; större poäng är bättre, och summan av de tre poäng är en sammansatt poäng. Våra riktmärken visade att ClusterONE överträffade de andra tillvägagångssätten både på viktade och oviktade PPI-nätverk, vilket matchade fler komplex med högre noggrannhet och gav en bättre en-till-en kartläggning med referenskomplex i nästan alla datamängder. MCL gav den närmaste poängen till ClusterONE. Men MCL kan inte hantera överlappningar. Den senaste utvecklingen i försöksförfaranden har resulterat i publicering av många högkvalitativa, storskaliga proteinproteininteraktionsdata (PPI) för olika organismer. Dessa data kan representeras som oriktade grafer, i vilka noder representerar proteiner och kanter representerar interaktioner mellan par av proteiner. Ofta finns det en uppskattning av tillförlitligheten hos sådana interaktioner och ingår som eggetiketter (vikter). Man kan formulera problemet med att identifiera proteinkomplex från PPI-data som att upptäcka täta regioner som innehåller många anslutningar i PPI-nätverk (eller regioner med stora vikter i viktade nätverk). Densely anslutna regioner i grafer är oftast identifieras med vissa oövervakade kluster metod 1,2. Standardklustring är dock inte idealisk för PPI-nätverk: proteiner kan ha flera funktioner, och därför kan motsvarande noder tillhöra mer än ett kluster; till exempel 207 av 1 628 proteiner i CYC2008 handkurerade jästkomplex data set 3 delta i mer än ett komplex. Sådana noder utgör en utmaning för klassiska graf kluster algoritmer som tilldelar varje nod av grafen till bara en av kluster. Nyligen har algoritmer föreslagits som upptäcker överlappande kluster, men i många fall är de begränsade till oviktade PPI-data 4,5 och kan tillämpas på vägda nätverk endast efter "binarisering" dem genom att ta bort kanter med vikter under en given tröskel. Även om det är svårt att bedöma tillförlitligheten av en enda kant vikt, fann vi att med hänsyn till nätverksvikter kan avsevärt förbättra upptäckten av proteinkomplex (kompletterande diskussioner och kompletterande figurer. 1 och 2) Därför bör vikter användas när sådana finns tillgängliga.  Vi ger också resultat med hjälp av referensuppsättningen som härleds från Gene Ontology-anteckningarna i SGD och de förväntade värdena för varje poäng för randomiserade predikterade komplexa uppsättningar (kompletterande diskussion och kompletterande bild. 3)............................................................... För att undersöka den biologiska relevansen av förutsagda komplex beräknade vi "co-localization" poäng för hela den förutsagda komplexa uppsättningen och genomförde överrepresentationsanalys av Gene Ontology annoteringar för varje förutsagt komplex. Eftersom MCL gav den närmaste poängen till Clusterone i MIPS-riktmärken, presenterar vi dessa poäng för ClusterONE och MCL (kompletterande tabellerna 1 och 2). Resultat för ClusterONE indikerade att förutsagda komplex tenderade att bestå av proteiner i samma cellkomponent och dessa proteiner är sannolikt att ha liknande funktioner och / eller delta i samma biologiska process. Jämförelse av co-localization och overrepresentation scores av ClusterONE och MCL visade att ClusterONE komplex hade högre poäng på nästan alla dataset. Vi presenterar ett exempel på hur ett par komplex med en känd överlappning upptäcktes av ClusterONE och MCL (Fig. Avsnitt 3A001.a.1.a.1 ska ändras på följande sätt:
Nepusz m.fl. REF föreslog ClusterOne algoritm för att upptäcka överlappande kluster som är mycket lik MCODE genom att starta från en enda frövertex. Men algoritmen slår samman varje par av grupper där överlappningen poäng är över en angiven tröskel.