Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Simultaneous identification of duplications and lateral transfers
KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
2004 (English)In: Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB, 2004, p. 347-356Conference paper, Published paper (Refereed)
Abstract [en]

This paper introduces a combinatorial model that incorporates duplication events as well as lateral gene transfer events (a.k.a. horizontal gene transfer events). To the best of our knowledge, this is the first such model containing both of these events. A so-called dt-scenario is used to explain differences between a gene tree T and species trees S. The model is biologically as well as mathematically sound. Among other biological considerations, the model respects the partial order of evolution implied by 5 by demanding that the dt-scenarios are "acyclic". We present fixed parameter tractable algorithms that count the minimum number of duplications and lateral transfers, and more generally can compute the set of pairs (t, d) where d is the minimum number of duplications required by any explanation that requires t lateral transfers. This allows us to also compute a weighted parsimony score. We also show how gene loss events can be incorporated into our model. We also give an NP-completeness proof which suggests that the intractability is due to the demand that the dt-scenarios be acyclic. When this condition is removed, we can show that the problem is computable in polynomial time via dynamic programming. By generating "synthetic" gene and species trees via a birth-death process, we explored the capacity of our algorithms to faithfully reconstruct the actual number of events taken place. The results are positive.

Place, publisher, year, edition, pages
2004. p. 347-356
Series
Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB ; 8
Keywords [en]
Gene duplication, Gene loss, Lateral gene transfer, Algorithms, Computational methods, Computer simulation, Dynamic programming, Genes, Mapping, Parameter estimation, Problem solving, Species trees, Genetic engineering
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-157445Scopus ID: 2-s2.0-2442573762OAI: oai:DiVA.org:kth-157445DiVA, id: diva2:770800
Conference
RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology, 27 March 2004 through 31 March 2004, San Diego, CA.
Note

QC 20141211

Available from: 2014-12-11 Created: 2014-12-09 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Search in DiVA

By author/editor
Lagergren, Jens
By organisation
Microelectronics and Information Technology, IMIT
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 12 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf