Effective identification of conserved pathways in biological networks using hidden Markov models.
BACKGROUND
The advent of various high-throughput experimental techniques for measuring molecular interactions has enabled the systematic study of biological interactions on a global scale. Since biological processes are carried out by elaborate collaborations of numerous molecules that give rise to a complex network of molecular interactions, comparative analysis of these biological networks can bring important insights into the functional organization and regulatory mechanisms of biological systems.


RESULTS
In this paper, we present an effective framework for identifying common interaction patterns in the biological networks of different organisms based on hidden Markov models (HMMs). Given two or more networks, our method efficiently finds the top matching paths in the respective networks, where the matching paths may contain a flexible number of consecutive insertions and deletions.


CONCLUSIONS
Based on several protein-protein interaction (PPI) networks obtained from the Database of Interacting Proteins (DIP) and other public databases, we demonstrate that our method is able to detect biologically significant pathways that are conserved across different organisms. Our algorithm has a polynomial complexity that grows linearly with the size of the aligned paths. This enables the search for very long paths with more than 10 nodes within a few minutes on a desktop computer. The software program that implements this algorithm is available upon request from the authors.
Qian
Xiaoning
X
Department of Computer Science and Engineering, University of South Florida, Tampa, Florida, United States of America.
Yoon
Byung-Jun
BJ
D000818:Animals; D001419:Bacteria / Q000378:metabolism; D001426:Bacterial Proteins / Q000378:metabolism; D029721:Drosophila Proteins / Q000378:metabolism; D004331:Drosophila melanogaster / Q000378:metabolism; D006801:Humans; D008390:Markov Chains; D008954:Models, Biological; D011485:Protein Binding; D015398:Signal Transduction
D001426:Bacterial Proteins; D029721:Drosophila Proteins