Bakgrund: Integrering och analys av heterogena genomskaliga data är en enorm algoritmisk utmaning för modern systembiologi. Bipartita grafer kan vara användbara för att representera relationer över par av olika datatyper, med tolkningen av dessa relationer åstadkoms genom en uppräkning av maximal bicliques. De flesta tidigare kända tekniker är i allmänhet dåligt lämpade för denna grundläggande uppgift, eftersom de är relativt ineffektiva och utan effektiv skalning. I detta papper, en kraftfull ny algoritm beskrivs som producerar alla maximal bicliques i en bipartite graf. Till skillnad från de flesta tidigare tillvägagångssätt innebär den nya metoden varken onödiga begränsningar av dess input eller att problemstorleken ökar. Effektivitet uppnås genom ett innovativt utnyttjande av bipartitgrafikstrukturen, och genom beräkningsminskningar som snabbt eliminerar icke-maximala kandidater från sökytan. Ett iterativt urval av hörn för övervägande baserat på icke-minska gemensamma stadsdelsstorlekar ökar effektiviteten och leder till mer balanserade rekursion träd. Resultat: Den nya tekniken implementeras och jämförs med tidigare publicerade metoder från grafteori och datautvinning. Formella tid- och rymdgränser härleds. Experiment utförs på både slumpmässiga grafer och grafer konstruerade av funktionell genomik data. Det har visat sig att den nya metoden avsevärt överträffar de bästa tidigare alternativen. Den nya metoden är strömlinjeformad, effektiv och särskilt väl lämpad för studier av enorma och varierande biologiska data. Ett robust genomförande har införlivats i GeneWeaver, ett onlineverktyg för att integrera och analysera funktionella genomiska experiment, som finns på http://geneweaver.org. Den enorma ökningen av skalbarheten ger användarna möjlighet att studera komplexa och tidigare oantastliga genuppsättningar mellan gener och deras biologiska funktioner i hierarkisk och genomomfattande skala. Denna praktiska beräkningsresurs kan anpassas till nästan alla tillämpningar där tvåpartsgrafer kan användas för att modellera relationer mellan par av heterogena enheter.
Nyligen, Zhang et al. REF introducerade iMBEA algoritmen för uppräkning av maximal bicliques i en bipartite graf.
On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types
{'venue': 'BMC Bioinformatics', 'journal': 'BMC Bioinformatics', 'mag_field_of_study': ['Computer Science', 'Medicine']}