2010/03/05 by Louxin Zhang, Zhang, Louxin · 4 citations
Biochemistry, Genetics and Molecular Biology · Mathematics · #Artificial intelligence #Binary tree #Bioinformatics and Genomic Networks #Biology #Coalescence (physics) #Coalescent theory #Combinatorics #Computational biology #Computer science #Evolutionary biology #FOS: Biological sciences #Gene #Gene duplication #Gene expression and cancer classification #Genetics #Genomics and Phylogenetic Studies #Inference #K-ary tree #Mathematics #Phylogenetic tree #Populations and Evolution (q-bio.PE) #Quantitative Methods (q-bio.QM) #Tree (set theory) #Tree rearrangement #Tree structure #q-bio.PE #q-bio.QM
paper · pdf · doi:10.48550/arxiv.1003.1204
published in arXiv (Cornell University) (Cornell University) · 17 pages 6 figures
arxiv created 2010/03/05 · arxiv updated 2010/03/05 · openalex publication_date 2010/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
When gene copies are sampled from various species, the resulting gene tree might disagree with the containing species tree. The primary causes of gene tree and species tree discord include lineage sorting, horizontal gene transfer, and gene duplication and loss. Each of these events yields a different parsimony criterion for inferring the (containing) species tree from gene trees. With lineage sorting, species tree inference is to find the tree minimizing extra gene lineages that had to coexist along species lineages; with gene duplication, it becomes to find the tree minimizing gene duplications and/or losses. In this paper, we show the following results: (i) The deep coalescence cost is equal to the number of gene losses minus two times the gene duplication cost in the reconciliation of a uniquely leaf labeled gene tree and a species tree. The deep coalescence cost can be computed in linear time for any arbitrary gene tree and species tree. (ii) The deep coalescence cost is always no less than the gene duplication cost in the reconciliation of an arbitrary gene tree and a species tree. (iii) Species tree inference by minimizing deep coalescences is NP-hard.