Research PapersNo Access

A FAST AND ACCURATE ALGORITHM FOR COMPARATIVE ANALYSIS OF METABOLIC PATHWAYS

FERHAT AY

Department of Computer Science and Engineering, University of Florida, Gainesville, FL 32611, USA

Search for more papers by this author

TAMER KAHVECI

Department of Computer Science and Engineering, University of Florida, Gainesville, FL 32611, USA

Search for more papers by this author

and

VALÉRIE DE CRÉCY-LAGARD

Department of Microbiology and Cell Science, University of Florida, Gainesville, FL 32611, USA

Search for more papers by this author

https://doi.org/10.1142/S0219720009004163Cited by:12

Abstract

Pathways show how different biochemical entities interact with one another to perform vital functions for the survival of an organism. Comparative analysis of pathways is crucial in identifying functional similarities that are difficult to identify by comparing individual entities that build up these pathways. When interacting entities are of single type, the problem of identifying similarities by aligning the pathways can be reduced to graph isomorphism problem. For pathways with varying types of entities such as metabolic pathways, alignment problem is even more challenging. In order to simplify this problem, existing methods often reduce metabolic pathways to graphs with restricted topologies and single type of nodes. However, these abstractions reduce the relevance of the alignment significantly as they cause losses in the information content. In this paper, we describe an algorithm to solve the pairwise alignment problem for metabolic pathways. A distinguishing feature of our method is that it aligns different types of entities, such as enzymes, reactions and compounds. Also, our approach is free of any abstraction in modeling the pathways. We pursue the intuition that both pairwise similarities of entities (homology) and the organization of their interactions (topology) are important for metabolic pathway alignment. In our algorithm, we account for both by creating an eigenvalue problem for each entity type. We enforce the consistency while combining the alignments of different entity types by considering the reachability sets of entities. Our experiments show that our method finds biologically and statistically significant alignments in the order of milliseconds.

Availability: Our software and the source code in C programming language is available at .

Keywords:

References

H. Ogataet al., Nucleic Acids Res. 27(1), 29 (1999), DOI: 10.1093/nar/27.1.29. Crossref, Medline, Google Scholar
I. M. Keseleret al., Nucleic Acids Res. 33, 334 (2005), DOI: 10.1093/nar/gki108. Crossref, Google Scholar
L. Salwinskiet al., Nucleic Acids Res. 32(90001), D449 (2004), DOI: 10.1093/nar/gkh086. Crossref, Medline, Google Scholar
P. Sridhar, T. Kahveci and S. Ranka, Pac. Symp. Biocomput. 12, 88 (2007). Google Scholar
C. Francke, R. J. Siezen and B. Teusink, Trends Microbiol. 13(11), 550 (2005), DOI: 10.1016/j.tim.2005.09.001. Crossref, Medline, Google Scholar
J. C. Clemente, K. Satou and G. Valiente, Genome Inform. 17(2), 46 (2006). Medline, Google Scholar
M. Heymans and A. Singh, Bioinformatics 19, 138 (2003), DOI: 10.1093/bioinformatics/btg1018. Crossref, Medline, Google Scholar
P. Damaschke, Lect. Notes Comput. Sci. 484, 72 (1991). Crossref, Google Scholar
B. Dostet al., Qnet: A tool for querying protein interaction networks, Ann Int Conf Res Comput Mol Biol (RECOMB) (2007) pp. 1–15. Google Scholar
Y. Tohsato and Y. Nishimura, IPSJ Digital Courier 3, 736 (2007), DOI: 10.2197/ipsjdc.3.736. Crossref, Google Scholar
R. Y. Pinteret al., Bioinformatics 21(16), 3401 (2005), DOI: 10.1093/bioinformatics/bti554. Crossref, Medline, Google Scholar
M. Koyutürk, A. Grama and W. Szpankowski, ECCB 200 (2004). Google Scholar
R. Singh, J. Xu and B. Berger, RECOMB 16 (2007). Google Scholar
R. Singh, J. Xu and B. Berger, Proc. Natl. Acad. Sci. USA 105, 12763 (2008), DOI: 10.1073/pnas.0806627105. Crossref, Medline, Google Scholar
J. M. Kleinberg, Journal of the ACM 46(5), 604 (1999), DOI: 10.1145/324133.324140. Crossref, Google Scholar
J. C. Clemente, K. Satou and G. Valiente, Bioinformatics 23(2), e110 (2007), DOI: 10.1093/bioinformatics/btl307. Crossref, Medline, Google Scholar
D. L. Wheeleret al., Nucleic Acids Res. 28(1), 10 (2000), DOI: 10.1093/nar/28.1.10. Crossref, Medline, Google Scholar
J. Wanget al., Evol. Bioinform. 1, 37 (2005). Medline, Google Scholar
J. Felsenstein, Cladistics 5, 164 (1989). Google Scholar
M. Koyutürk, A. Grama and W. Szpankowski, RECOMB 48 (2005). Google Scholar
M. Narayanan and R. M. Karp, J. Comput. Biol. 14(7), 892 (2007), DOI: 10.1089/cmb.2007.0025. Crossref, Medline, Google Scholar
J. Berg and M. Lssig, Proc. Natl. Acad. Sci. USA 101(41), 14689 (2004), DOI: 10.1073/pnas.0305199101. Crossref, Medline, Google Scholar
J. Dutkowski and J. Tiuryn, Bioinformatics 23(13), i149 (2007), DOI: 10.1093/bioinformatics/btm194. Crossref, Medline, Google Scholar
E. C. Webb , Enzyme Nomenclature 1992 ( Academic Press , 1992 ) . Google Scholar
Y. Tohsato, H. Matsuda and A. Hashimoto, ISMB 376 (2000). Google Scholar
R. Somogyi and C. A. Sniegoski, Complexity 1, 45 (1996). Crossref, Google Scholar
S. A. Kauffman , The Origins of Order: Self-Organization and Selection in Evolution ( Oxford University Press , 1993 ) . Google Scholar
D. Thieffry, M. Colet and R. Thomas, Math Modelling Sci. Computing 2, 144 (1993). Google Scholar
R. Thomas, D. Thieffry and M. Kaufmaun, Bulletin of Mathematical Biology (1995). Google Scholar
A. Arkin, J. Ross and H. H. McAdams, Genetics 149(4), 1633 (1998). Medline, Google Scholar
D. T. Gillespie, J. Phys. Chem. 81, 2340 (1977), DOI: 10.1021/j100540a008. Crossref, Google Scholar
J. S. Edwards and B. O. Palsson, in silico 1(1), (2000). Google Scholar
M. Imielinskiet al., Bioinformatics 21(9), 2008 (2005), DOI: 10.1093/bioinformatics/bti245. Crossref, Medline, Google Scholar
V. Hatzimanikatiset al., Curr. Opin. Struct. Biol. 14, 300 (2004), DOI: 10.1016/j.sbi.2004.04.004. Crossref, Medline, Google Scholar
N. Friedmanet al., J. Comput. Biol. 7(3-4), 601 (2000), DOI: 10.1089/106652700750050961. Crossref, Medline, Google Scholar
J. Pearl , Probabilistic Reasoning in Intelligent Systems ( Morgan Kaufmann , 1988 ) . Google Scholar
L. Krishnamurthyet al., Bioinformatics 19(8), 930 (2003), DOI: 10.1093/bioinformatics/btg113. Crossref, Medline, Google Scholar
T. Dwyer, H. Rolletschek and F. Schreiber, APBC 13 (2004). Google Scholar
H. Xionget al., Pac. Symp. Biocomput. 10, 221 (2005). Google Scholar
E. Sharon and E. Segal, RECOMB 77 (2007). Google Scholar
H. W. Maet al., Bioinformatics 20(12), 1870 (2004), DOI: 10.1093/bioinformatics/bth167. Crossref, Medline, Google Scholar
M. Hattoriet al., J. Am. Chem. Soc. 125(39), 11853 (2003), DOI: 10.1021/ja036030u. Crossref, Medline, Google Scholar
Haveliwala TH, Kamvar SD, The second eigenvalue of the google matrix, Stanford University Technical Report, March 2003 . Google Scholar
J. Kim and S. D. Copley, Biochemistry 46(44), (2007). Google Scholar
A. J. McCoyet al., Proc. Natl. Acad. Sci. USA 103(47), 17909 (2006), DOI: 10.1073/pnas.0608643103. Crossref, Medline, Google Scholar
M. L. Green and P. D. Karp, BMC Bioinformatics 5, 76 (2004), DOI: 10.1186/1471-2105-5-76. Crossref, Medline, Google Scholar
P. Sridharet al., PSB 291 (2008). Google Scholar
B. Songet al., Int. J. Data Mining Bioinform. 3(2), 124 (2009), DOI: 10.1504/IJDMB.2009.024847. Crossref, Medline, Google Scholar
N. Saitou and M. Nei, Mol. Biol. Evol. 4(4), 406 (1987). Medline, Google Scholar
J. C. Clemente, K. Satou and G. Valiente, Genome Inform. 16(2), 45 (2005). Medline, Google Scholar
D. R. Robinson and L. R. Foulds, Math Biosci. 53, 131 (1981), DOI: 10.1016/0025-5564(81)90043-2. Crossref, Google Scholar
P. Romeroet al., Genome Biol. 6(1), (2005), DOI: 10.1186/gb-2005-6-8-r66. Google Scholar

Vol. 07, No. 03

Metrics

Downloaded 39 times

History

Received 18 July 2008

Revised 25 November 2008

Accepted 26 November 2008

Keywords

PDF download

System Upgrade on Mon, Jun 21st, 2021 at 1am (EDT)

A FAST AND ACCURATE ALGORITHM FOR COMPARATIVE ANALYSIS OF METABOLIC PATHWAYS

Abstract

References

Recommended