Algorithms to Detect Multiprotein Modularity Conserved During Evolution
| Title | Algorithms to Detect Multiprotein Modularity Conserved During Evolution |
| Publication Type | Journal Article |
| Year of Publication | 2011 |
| Authors | Hodgkinson, L., & Karp R. M. |
| Published in | IEEE/ACM Transactions on Computational Biology and Bioinformatics |
| Other Numbers | 3230 |
| Abstract | Detecting essential multiprotein modules that change infrequently during evolution is a challenging algorithmic task that isimportant for understanding the structure, function, and evolution of the biological cell. In this paper, we define a measure of modularityfor interactomes and present a linear-time algorithm, Produles, for detecting multiprotein modularity conserved during evolution thatimproves on the running time of previous algorithms for related problems and offers desirable theoretical guarantees. We presenta biologically motivated graph theoretic set of evaluation measures complementary to previous evaluation measures, demonstratethat Produles exhibits good performance by all measures, and describe certain recurrent anomalies in the performance of previousalgorithms that are not detected by previous measures. Consideration of the newly defined measures and algorithm performance onthese measures leads to useful insights on the nature of interactomics data and the goals of previous and current algorithms. Throughrandomization experiments we demonstrate that conserved modularity is a defining characteristic of interactomes. Computationalexperiments on current experimentally derived interactomes for Homo sapiens and Drosophila melanogaster, combining results across |
| Acknowledgment | This work was partially supported by funding provided to ICSI through National Science Foundation grant IIS: 0803937 (III-CXT-Medium: Biological Data Integration Using Large-Scale Molecular Interation Networks). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the National Science Foundation. |
| URL | http://www.icsi.berkeley.edu/pubs/algorithms/multiproteinmodularity11.pdf |
| Bibliographic Notes | IEEE/ACM Transactions on Computational Biology and Bioinformatics, PMID: 21968956 |
| Abbreviated Authors | L. Hodgkinson and R. M. Karp |
| ICSI Research Group | Algorithms |
| ICSI Publication Type | Article in journal or magazine |