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 specify gene clusters—groups of genes that are co-located in a set of genomes. Several approaches have been proposed to reconstruct putative ancestral gene clusters based on the gene order of contemporary species. One prevalent and natural reconstruction criterion is consistency: For a set of reconstructed gene clusters, there should exist a gene order that comprises all given clusters. For permutation-based gene cluster models, efficient methods exist to verify this condition. In this article, we discuss the consistency problem for different gene cluster models on sequences with restricted gene multiplicities. Our results range from linear-time algorithms for the simple model of adjacencies to NP-completeness proofs for more complex models like common intervals.
Get full access to this article
View all access options for this article.
References
1.
AdamZ., TurmelM., LemieuxC.et al.2007. Common intervals and symmetric difference in a model-free phylogenomics, with an application to streptophyte evolution. J. Comput. Biol., 14:436–445.
2.
BergeronA., StoyeJ.2006. On the similarity of sets of permutations and its applications to genome comparison. J. Comput. Biol., 13:1340–1354.
3.
BergeronA., BlanchetteM., ChateauA.et al.2004. Reconstructing ancestral gene order using conserved intervals. Lect. Notes Bioinform., 3240:14–25.
4.
BergeronA., ChauveC., GingrasY.2008. Formal models of gene clusters. MăndoiuA.Z.I.Bioinformatics Algorithms: Techniques and Applications. Wiley Book Series on Bioinformatics: Wiley, New York.
5.
BhutkarA., GelbartW.M., SmithT.F.2007. Inferring genome-scale rearrangement phylogeny and ancestral gene order: Drosophila case study. Genome Biol., 8:R236.
6.
BlinG., FayeD., StoyeJ.2010. Finding nested common intervals efficiently. J. Comput. Biol., 17:1183–1194.
7.
BöckerS., JahnK., MixtackiJ.et al.2009. Computation of median gene clusters. J. Comput. Biol., 16:1085–1099.
8.
BoothK.S., LuekerG.S.1976. Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci., 13:335–379.
9.
ChauveC., TannierE.2008. A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes. PLoS Comput. Biol., 4:e1000234.
10.
ChauveC., MaňuchJ., PattersonM.2009. On the gapped consecutive-ones property. ENDM, 34:121–125.
11.
CsűrösM., MiklósI.2009. Mathematical framework for phylogenetic birth-and-death models. Arxiv(preprint arXiv:0902.0970).
12.
DurandD., SankoffD.2002. Tests for gene clustering. Proc RECOMB 2002, 144–154.
13.
FriedmanR., HughesA.L.2001. Gene duplication and the structure of eukaryotic genomes. Genome Res., 11:373–381.
14.
GoldbergP., GolumbicM., KaplanH.et al.1995. Four strikes against physical mapping of DNA. J. Comput. Biol., 2:139–152.
15.
HabibM., McConnellR., PaulC.et al.2000. Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci., 234:59–84.
16.
HaddadiS.2002. A note on the NP–hardness of the consecutive block minimization problem. Int. Trans. Oper. Res., 9:775–777.
17.
HeX., GoldwasserM.H.2005. Identifying conserved gene clusters in the presence of homology families. J. Comput. Biol., 12:638–656.
18.
HobermanR., DurandD.2005. The incompatible desiderata of gene cluster properties. Lect. Notes Bioinform, 3678:73–87.
19.
HsuW.-L.2002. A simple test for the consequtive ones property. J. Algorithms, 43:1–16.
20.
HsuW.-L., McConnellR.2004. PQ-trees, PC-trees, and planar graphs. MehtaD.P., SahniS.Handbook of Data Structures and Applications: Wiley, New York.
21.
HuynenM.A., SnelB., BorkP.2001. Inversions and the dynamics of eukaryotic gene order. Trends Genet., 17:304–306.
22.
JaillonO., AuryJ.-M., BrunetF.2004. Genome duplication in the teleost fish tetraodon nigroviridis reveals the early vertebrate proto-karyotype. Nature, 431:946–957.
23.
LawrenceJ.G., RothJ.R.1996. Selfish operons: horizontal transfer may drive the evolution of gene clusters. Genetics, 143:1843–1860.
24.
MaJ., ZhangL., SuhB.B.et al.2006. Reconstructing contiguous regions of an ancestral genome. Genome Res., 16:1557–1565.
25.
MaňuchJ, PattersonM. 2010. The complexity of the gapped consecutive-ones property problem for matrices of bounded maximum degree. Lect. Notes Bioinform., 6398:278–289.
26.
OverbeekR., FonsteinM., D'SouzaM.et al.1999. The use of gene clusters to infer functional coupling. Proc. Natl. Acad. Sci. USA, 96:2896–2901.
27.
PageR.D.M., CharlestonM.A.1997. From gene to organismal phylogeny: reconciled trees and the gene tree/species tree problem. Mol. Phylogenet. Evol., 7:231–240.
