Gene tree correction for reconciliation and species tree inference: Complexity and algorithms

Abby, 2012, Lateral gene transfer as a support for the tree of life, Proceedings of the National Academy of Sciences of the United States of America, 109, 4962, 10.1073/pnas.1116871109 Aho, 1981, Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions, SIAM Journal on Computing, 10, 405, 10.1137/0210030 Akerborg, 2009, Simultaneous bayesian gene tree reconstruction and reconciliation analysis, Proceedings of the National Academy of Sciences of the United States of America, 106, 5714, 10.1073/pnas.0806251106 Alimonti, 2000, Some APX-completeness results for cubic graphs, Theoretical Computer Science, 237, 123, 10.1016/S0304-3975(98)00158-3 Arvestad, 2004, Gene tree reconstruction and orthology analysis based on an integrated model for duplications and sequence evolution, 326 Berry, 2007, Maximum agreement and compatible supertrees, Journal of Discrete Algorithms, 5, 564, 10.1016/j.jda.2006.08.005 Blin, 2012, Complexity insights of the minimum duplication problem, vol. 7147, 153 Bonizzoni, 2005, Reconciling a gene tree to a species tree under the duplication cost model, Theoretical Computer Science, 347, 36, 10.1016/j.tcs.2005.05.016 Boussau, 2013, L.D.: Genome-scale coestimation of species and gene trees, Genome Research, 23, 323, 10.1101/gr.141978.112 Bryant, 1997 Byrka, 2010, New results on optimizing rooted triplets consistency, Discrete Applied Mathematics, 158, 1136, 10.1016/j.dam.2010.03.004 Chauve, 2009, New perspectives on gene family evolution: losses in reconciliation and a link with supertrees, vol. 5541, 46 Chen, 2000, Notung: Dating gene duplications using gene family trees, Journal of Computational Biology, 7, 429, 10.1089/106652700750050871 Chung, 2011, Comparing two bayesian methods for gene tree/species tree reconstruction: Simulations with incomplete lineage sorting and horizontal gene transfer, Systematic Biology, 60, 261, 10.1093/sysbio/syr003 Dondi, 2012, Minimum leaf removal for reconciliation: Complexity and algorithms, vol. 7354, 399 Doroftei, 2011, Removing noise from gene trees, vol. 6833, 76 Doyon, 2011, Models, algorithms and programs for phylogeny reconciliation, Briefings in Bioinformatics, 12, 392, 10.1093/bib/bbr045 Durand, 2006, A hybrid micro-macroevolutionary approach to gene tree reconstruction, Journal of Computational Biology, 13, 320, 10.1089/cmb.2006.13.320 Fang, 2010, Getting started in gene orthology and functional analysis, PLoS Computational Biology, 6, e1000703, 10.1371/journal.pcbi.1000703 Goodman, 1979, Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences, Systematic Zoology, 28, 132, 10.2307/2412519 Górecki, 2011, A linear time algorithm for error-corrected reconciliation of unrooted gene trees, vol. 6674, 148 Gorecki, 2006, DLS-trees: a model of evolutionary scenarios, Theoretical Computer Science, 359, 378, 10.1016/j.tcs.2006.05.019 Guigó, 1996, Reconstruction of ancient molecular phylogeny, Molecular Phylogenetics and Evolution, 6, 189, 10.1006/mpev.1996.0071 Hahn, 2007, Bias in phylogenetic tree reconciliation methods: implications for vertebrate genome evolution, Genome Biology, 8, R141, 10.1186/gb-2007-8-7-r141 Li, 2006, TreeFam: a curated database of phylogenetic trees of animal gene families, Nucleic Acids Research, 34, D572, 10.1093/nar/gkj118 Ma, 2000, From gene trees to species trees, SIAM Journal on Computing, 30, 729, 10.1137/S0097539798343362 Niedermeier, 2006 Ohno, 1970 Page, 1994, Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas, Systematic Biology, 43, 58 Page, 1997, Reconciled trees and incongruent gene and species trees, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 37, 57, 10.1090/dimacs/037/04 Rasmussen, 2011, A bayesian approach for fast and accurate gene tree reconstruction, Molecular Biology and Evolution, 28, 273, 10.1093/molbev/msq189 Sanderson, 2007, Inferring angiosperm phylogeny from EST data with widespread gene duplication, BMC Evolutionary Biology, 7, S3, 10.1186/1471-2148-7-S1-S3 Scornavacca, 2009, From gene trees to species trees through a supertree approach, vol. 5457, 702 Swenson, 2012, Gene tree correction for reconciliation and species tree inference, Algorithms for Molecular Biology, 7, 31, 10.1186/1748-7188-7-31 Thomas, 2010, GIGA: a simple, efficient algorithm for gene tree inference in the genomic age, BMC Bioinformatics, 11, 312, 10.1186/1471-2105-11-312 Thomas, 2003, A.K.: PANTHER: a library of protein families and subfamilies indexed for function, Genome Research, 13, 2129, 10.1101/gr.772403 Wapinski, 2007, Natural history and evolutionary principles of gene duplication in fungi, Nature, 449, 54, 10.1038/nature06107 Yu, 2012, The probability of a gene tree topology within a phylogenetic network with applications to hybridization detection, PLoS Genetics, 8, e1002660, 10.1371/journal.pgen.1002660