IEEE/ACM Transactions on Computational Biology and Bioinformatics · 2009 · 34 citations · 20 references
Life SciencesBioinformaticsEvolutionary BiologyComparative GenomicsGenomicsPhylogeneticsEvolutionary RelationshipsGene ClustersMolecular PhylogeneticsPhylogenetic AnalysisPhylogenetic Tree ReconstructionPhylogenomic AnalysisAncestral Gene Tree ReconstructionAncient Genome ReconstructionGene Order AnalysisGene Tree ReconstructionPhylogenetic GenomicsPhylogenetic GroupingPhylogenetic Inference From Gene OrderWorst-case Complexity
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.
20
The COG database: an updated version includes eukaryotes
Roman L. Tatusov, Natalie D. Fedorova, John D. Jackson et al. · BMC Bioinformatics · 2003 · 4.5K citations · Full text