title: Simultaneous identification of duplications and lateral gene transfers.
abstract: The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where so-called DTL-scenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTL-scenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTL-scenarios is NP-hard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixed-parameter tractable algorithm for finding most parsimonious DTL-scenarios.
authors.affiliation: KTH Royal Institute of Technology, Department of Computational Biology, Stockholm, Sweden. alix.tofigh@gmail.com
authors.forename: Ali
authors.initials: A
authors.lastname: Tofigh
authors.forename: Michael
authors.initials: M
authors.lastname: Hallett
authors.forename: Jens
authors.initials: J
authors.lastname: Lagergren
mesh_terms: D000465:Algorithms; D019143:Evolution, Molecular; D020440:Gene Duplication; D022761:Gene Transfer, Horizontal / Q000235:genetics*; D008957:Models, Genetic