Algorithms to Detect Multiprotein Modularity Conserved During Evolution

TitleAlgorithms to Detect Multiprotein Modularity Conserved During Evolution
Publication TypeJournal Article
Year of Publication2011
AuthorsHodgkinson, L., & Karp R. M.
Published inIEEE/ACM Transactions on Computational Biology and Bioinformatics
Other Numbers3230

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


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.

Bibliographic Notes

IEEE/ACM Transactions on Computational Biology and Bioinformatics, PMID: 21968956

Abbreviated Authors

L. Hodgkinson and R. M. Karp

ICSI Research Group


ICSI Publication Type

Article in journal or magazine