A Unified Approach for Reconstructing Ancient Gene Clusters

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Unified Approach for Reconstructing Ancient Gene Clusters

Full text

Pdf (2.56 MB)

Source

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) archive
Volume 6 , Issue 3 (July 2009) table of contents

Pages 387-400

Year of Publication: 2009

ISSN:1545-5963

Authors

Jens Stoye	Bielefeld University, Bielefeld
Roland Wittler	Bielefeld University, Bielefeld

Publisher

IEEE Computer Society Press Los Alamitos, CA, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 48, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/TCBB.2008.135

ABSTRACT

The order of genes in genomes provides extensive information. In comparative genomics, differences or similarities of gene orders are determined to predict functional relations of genes or phylogenetic relations of genomes. For this purpose, various combinatorial models can be used to identify gene clusters—groups of genes that are colocated in a set of genomes. We introduce a unified approach to model gene clusters and define the problem of labeling the inner nodes of a given phylogenetic tree with sets of gene clusters. Our optimization criterion in this context combines two properties: parsimony, i.e., the number of gains and losses of gene clusters has to be minimal, and consistency, i.e., for each ancestral node, there must exist at least one potential gene order that contains all the reconstructed clusters. We present and evaluate an exact algorithm to solve this problem. Despite its exponential worst-case time complexity, our method is suitable even for large-scale data. We show the effectiveness and efficiency on both simulated and real data.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	T. Dandekar, B. Snel, M. Huynen, and P. Bork, "Conservation of Gene Order: A Fingerprint of Proteins That Physically Interact," Trends in Biochemical Sciences, vol. 23, no. 9, pp. 324-328, 1998.
	2	R. Overbeek, M. Fonstein, M. D'Souza, G.D. Pusch, and N. Maltsev, "The Use of Gene Clusters to Infer Functional Coupling," Proc. Nat'l Academy of Sciences USA, vol. 96, no. 6, pp. 2896-2901, 1999.
	3	X. He and M.H. Goldwasser, "Identifying Conserved Gene Clusters in the Presence of Homology Families," J. Computational Biology, vol. 12, no. 6, pp. 638-656, 2005.
	4	S. Böcker, K. Jahn, J. Mixtacki, and J. Stoye, "Computation of Median Gene Clusters," Proc. 12th Ann. Int'l Conf. Research in Computational Molecular Biology (RECOMB '08), pp. 331-345, 2008.
	5	W.C. Lathe III, B. Snel, and P. Bork, "Gene Context Conservation of a Higher Order than Operons," Trends in Biochemical Sciences, vol. 25, no. 10, pp. 474-479, 2000.
	6	J. Tamames, "Evolution of Gene Order Conservation in Prokaryotes," Genome Biology, vol. 2, pp. research0020.1-research0027.11, 2001.
	7	J.G. Lawrence and J.R. Roth, "Selfish Operons: Horizontal Transfer May Drive the Evolution of Gene Clusters," Genetics, vol. 143, no. 4, pp. 1843-1860, 1996.
	8	R. Hoberman and D. Durand, "The Incompatible Desiderata of Gene Cluster Properties," Proc. Third Research in Computational Molecular Biology (RECOMB) Satellite Workshop Comparative Genomics (RECOMB-CG '05), 2005.
	9	A. Bergeron, C. Chauve, and Y. Gingras, "Formal Models of Gene Clusters," Bioinformatics Algorithms: Techniques and Applications, Wiley, 2007.
	10	A. Bergeron, M. Blanchette, A. Chateau, and C. Chauve, "Reconstructing Ancestral Gene Order Using Conserved Intervals," Proc. Fourth Int'l Workshop Algorithms in Bioinformatics (WABI '04), pp. 14-25, 2004.
	11	Z. Adam, M. Turmel, C. Lemieux, and D. Sankoff, "Common Intervals and Symmetric Difference in a Model-Free Phylogenomics, with an Application to Streptophyte Evolution," J. Computational Biology, vol. 14, no. 4, pp. 436-445, 2007.
	12	T. Uno and M. Yagiura, "Fast Algorithms to Enumerate All Common Intervals of Two Permutations," Algorithmica, vol. 26, no. 2, pp. 290-309, 2000.
	13	A. Bergeron and J. Stoye, "On the Similarity of Sets of Permutations and Its Applications to Genome Comparison," J. Computational Biology, vol. 13, no. 7, pp. 1340-1354, 2006.
	14	G.M. Landau, L. Parida, and O. Weimann, "Gene Proximity Analysis across Whole Genomes via PQ Trees," J. Computational Biology, vol. 12, no. 10, pp. 1289-1306, 2005.
	15	K.S. Booth and G.S. Lueker, "Testing for the Consecutive Ones Property, Interval Graphs and Graph Planarity Using PQ-Tree Algorithms," J. Computing and System Sciences, vol. 13, no. 3, pp. 335-379, 1976.
	16	W.M. Fitch, "Toward Defining the Course of Evolution: Minimum Change for a Specific Tree Topology," Systematic Zoology, vol. 20, no. 4, pp. 406-416, 1971.
	17	J.A. Hartigan, "Minimum Mutation Fits to a Given Tree," Biometrics, vol. 29, no. 1, pp. 53-65, 1973.
	18	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	19	Laxmi Parida, Pattern Discovery in Bioinformatics: Theory & Algorithms, Chapman & Hall/CRC, 2007
	20	D.L. Wheeler, C. Chappey, A.E. Lash, D.D. Leipe, T.L. Madden, G. Schuler, T.A. Tatusova, and B.A. Rapp, "Database Resources of the National Center for Biotechnology Information," Nucleic Acids Research, vol. 28, no. 1, pp. 10-14, 2000.
	21	D.A. Benson, I. Karsch-Mizrachi, D.J. Lipman, J. Ostell, B.A. Rapp, and D.L. Wheeler, "Genbank," Nucleic Acids Research, vol. 28, no. 1, pp. 15-18, 2000.
	22	R.L. Tatusov, E.V. Koonin, and D.J. Lipman, "A Genomic Perspective on Protein Families," Science, vol. 278, pp. 631-637, 1997.
	23	R.L. Tatusov, N.D. Fedorova, J.D. Jackson, A.R. Jacobs, B. Kiryutin, E.V. Koonin, D.M. Krylov, R. Mazumder, S.L. Mekhedov, A.N. Nikolskaya, B.S. Rao, S. Smirnov, A.V. Sverdlov, S. Vasudevan, Y.I. Wolf, J.J. Yin, and D.A. Natale, "The Cog Database: An Updated Version Includes Eukaryotes," BMC Bioinformatics, vol. 4, p. 41, 2003.
	24	M. Sugitaa, H. Sugishitaa, T. Fujishiroa, M. Tsuboia, C. Sugitaa, T. Endob, and M. Sugiura, "Organization of a Large Gene Cluster Encoding Ribosomal Proteins in the Cyanobacterium Synechococcus sp. Strain pcc 6301: Comparison of Gene Clusters among Cyanobacteria, Eubacteria and Chloroplast Genomes," Gene, vol. 195, no. 1, pp. 73-79, 1997.
	25	W.-L. Hsu and R. McConnell, "PC-Trees," Handbook of Data Structures and Applications, D.P. Mehta and S. Sahni, eds., 2003.
	26	Péter L. Erdős , László A. Székely, On weighted multiway cuts in trees, Mathematical Programming: Series A and B, v.65 n.1, p.93-105, May 31, 1994 [doi>10.1007/BF01581691]