Change search
ReferencesLink to record
Permanent link

Direct link
Simultaneous Identification of Duplications and Lateral Gene Transfers
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB.
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB.
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
Abstract [en]

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.
Keyword [en]
Trees, Biology and genetics, Combinatorial algorithms, Graph algorithms
National Category
Bioinformatics and Systems Biology Computer Science
URN: urn:nbn:se:kth:diva-10969DOI: 10.1109/TCBB.2010.14ISI: 000286146600021PubMedID: 21233529ScopusID: 2-s2.0-79551667938OAI: diva2:233570
QC 20100812 Uppdaterad från submitted till published(20110301)Available from: 2009-09-01 Created: 2009-09-01 Last updated: 2011-03-01Bibliographically approved
In thesis
1. Using Trees to Capture Reticulate Evolution: Lateral Gene Transfers and Cancer Progression
Open this publication in new window or tab >>Using Trees to Capture Reticulate Evolution: Lateral Gene Transfers and Cancer Progression
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The historic relationship of species and genes are traditionally depicted using trees. However, not all evolutionary histories are adequately captured by bifurcating processes and an increasing amount of research is devoted towards using networks or network-like structures to capture evolutionary history. Lateral gene transfer (LGT) is a previously controversial mechanism responsible for non tree-like evolutionary histories, and is today accepted as a major force of evolution, particularly in the prokaryotic domain.

In this thesis, we present models of gene evolution incorporating both LGTs and duplications, together with efficient computational methods for various inference problems. Specifically, we define a biologically sound combinatorial model for reconciliation of species and gene trees that facilitates simultaneous consideration of duplications and LGTs. We prove that finding most parsimonious reconciliations is NP-hard, but that the problem can be solved efficiently if reconciliations are not required to be acyclic—a condition that is satisfied when analyzing most real-world datasets. We also provide a polynomial-time algorithm for parametric tree reconciliation, a problem analogous to parametric sequence alignment, that enables us to study the entire space of optimal reconciliations under all possible cost schemes.

Going beyond combinatorial models, we define the first probabilistic model of gene evolution incorporating a birth-death process generating duplications, LGTs, and losses, together with a relaxed molecular clock model of sequence evolution. Algorithms based on Markov chain Monte Carlo (MCMC) techniques, methods from numerical analysis, and dynamic programming are presented for various probability and parameter inference problems.

Finally, we develop methods for analysis of cancer progression, a biological process with many similarities to the process of evolution. Cancer progresses by accumulation of harmful genetic aberrations whose patterns of emergence are graph-like. We develop a model of cancer progression based on trees, and mixtures thereof, that admits an efficient structural EM algorithm for finding Maximum Likelihood (ML) solutions from available cross-sectional data.

Place, publisher, year, edition, pages
Stockholm: KTH, 2009. viii, 68 p.
Trita-CSC-A, ISSN 1653-5723 ; 2009:10
Lateral Gene Tranfer, Horizontal Gene Transfer, Cancer Progression
National Category
Bioinformatics and Systems Biology Computer Science
urn:nbn:se:kth:diva-10608 (URN)978-91-7415-349-1 (ISBN)
Public defence
2009-06-12, Svedbergssalen, Albanova, Roslagstullsbacken 21, Stockholm, 10:00 (English)
QC 20100812Available from: 2009-06-04 Created: 2009-06-02 Last updated: 2010-08-12Bibliographically approved

Open Access in DiVA

fulltext(296 kB)407 downloads
File information
File name FULLTEXT01.pdfFile size 296 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textPubMedScopusCS, Digital library

Search in DiVA

By author/editor
Tofigh, AliLagergren, Jens
By organisation
Computational Biology, CB
In the same journal
IEEE/ACM Transactions on Computational Biology & Bioinformatics
Bioinformatics and Systems BiologyComputer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 407 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 172 hits
ReferencesLink to record
Permanent link

Direct link