Computation of Median Gene Clusters
Authors:
- 1 August 2009
- journal article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 16 (8) , 1085-1099
Abstract
Whole genome comparison based on gene order has become a popular approach in comparative genomics. An important task in this field is the detection of gene clusters, i.e., sets of genes that occur co-localized in several genomes. For most applications, it is preferable to extend this definition to allow for small deviations in the gene content of the cluster occurrences. However, relaxing the equality constraint increases the computational complexity of gene cluster detection drastically. Existing approaches deal with this problem by using simplifying constraints on the cluster definition and/or allowing only pairwise genome comparison. In this article, we introduce a cluster concept named median gene clusters that improves over existing models, present efficient algorithms for their computation and show experimental results on the detection of approximate gene clusters in multiple genomes.Keywords
This publication has 6 references indexed in Scilit:
- Improved approximate common intervalInformation Processing Letters, 2007
- Character sets of stringsJournal of Discrete Algorithms, 2007
- Identifying Conserved Gene Clusters in the Presence of Homology FamiliesJournal of Computational Biology, 2005
- Fixed-Parameter Algorithms for CLOSEST STRING and Related ProblemsAlgorithmica, 2003
- Fast Algorithms to Enumerate All Common Intervals of Two PermutationsAlgorithmica, 2000
- Conservation of gene order: a fingerprint of proteins that physically interactTrends in Biochemical Sciences, 1998