Title |
On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types
|
---|---|
Published in |
BMC Bioinformatics, April 2014
|
DOI | 10.1186/1471-2105-15-110 |
Pubmed ID | |
Authors |
Yun Zhang, Charles A Phillips, Gary L Rogers, Erich J Baker, Elissa J Chesler, Michael A Langston |
Abstract |
Integrating and analyzing heterogeneous genome-scale data is a huge algorithmic challenge for modern systems biology. Bipartite graphs can be useful for representing relationships across pairs of disparate data types, with the interpretation of these relationships accomplished through an enumeration of maximal bicliques. Most previously-known techniques are generally ill-suited to this foundational task, because they are relatively inefficient and without effective scaling. In this paper, a powerful new algorithm is described that produces all maximal bicliques in a bipartite graph. Unlike most previous approaches, the new method neither places undue restrictions on its input nor inflates the problem size. Efficiency is achieved through an innovative exploitation of bipartite graph structure, and through computational reductions that rapidly eliminate non-maximal candidates from the search space. An iterative selection of vertices for consideration based on non-decreasing common neighborhood sizes boosts efficiency and leads to more balanced recursion trees. |
X Demographics
Geographical breakdown
Country | Count | As % |
---|---|---|
Norway | 1 | 50% |
Unknown | 1 | 50% |
Demographic breakdown
Type | Count | As % |
---|---|---|
Members of the public | 1 | 50% |
Scientists | 1 | 50% |
Mendeley readers
Geographical breakdown
Country | Count | As % |
---|---|---|
United States | 3 | 3% |
Armenia | 1 | 1% |
Switzerland | 1 | 1% |
Unknown | 83 | 94% |
Demographic breakdown
Readers by professional status | Count | As % |
---|---|---|
Student > Ph. D. Student | 22 | 25% |
Researcher | 21 | 24% |
Student > Master | 9 | 10% |
Student > Bachelor | 6 | 7% |
Professor > Associate Professor | 6 | 7% |
Other | 14 | 16% |
Unknown | 10 | 11% |
Readers by discipline | Count | As % |
---|---|---|
Computer Science | 29 | 33% |
Agricultural and Biological Sciences | 14 | 16% |
Biochemistry, Genetics and Molecular Biology | 8 | 9% |
Mathematics | 6 | 7% |
Social Sciences | 5 | 6% |
Other | 14 | 16% |
Unknown | 12 | 14% |