Simultaneous Identification of Duplications and Lateral Gene Transfers
2011 (English)In: IEEE/ACM Transactions on Computational Biology & Bioinformatics, ISSN 1545-5963, E-ISSN 1557-9964, Vol. 8, no 2, 517-535 p.Article in journal (Refereed) Published
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 a so-called DTL-scenario is used to explain the differences between a gene tree anda corresponding species tree taking into account gene duplications, gene losses, and lateral genetransfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateralgene transfer may only occur between contemporary species leads to the notion of acyclic DTLscenarios.Parsimony methods are introduced by defining appropriate optimization problems. Weshow that finding most parsimonious acyclic DTL-scenarios is NP-complete. However, by droppingthe condition of acyclicity, the problem becomes tractable, and we provide a dynamic programmingalgorithm as well as a fixed-parameter-tractable algorithm for finding most parsimonious DTLscenarios.
Place, publisher, year, edition, pages
2011. Vol. 8, no 2, 517-535 p.
Trees, Biology and genetics, Combinatorial algorithms, Graph algorithms
Bioinformatics and Systems Biology Computer Science
IdentifiersURN: urn:nbn:se:kth:diva-10969DOI: 10.1109/TCBB.2010.14ISI: 000286146600021PubMedID: 21233529ScopusID: 2-s2.0-79551667938OAI: oai:DiVA.org:kth-10969DiVA: diva2:233570
Uppdaterad från submitted till published(20110301)2009-09-012009-09-012011-03-01Bibliographically approved