Change search
ReferencesLink to record
Permanent link

Direct link
Inferring Duplications and Lateral Gene Transfers: An Algorithm for Parametric Tree Reconciliation
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB.
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB.
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Prediction of the function of genes and their products is an increasingly important computational problem. The ability to correctly identify the historic relationship of homologous genes is essential for making accurate predictions.In 1970, Fitch made a distinction between paralogous and orthologous genes, its importance lying in the observation that genes are more likely to have similar functions when they have evolved from a common ancestral gene through speciation rather than duplication. Lateral gene transfer (LGT) is yet another important evolutionary event that creates copies of genes, and asour understanding of the importance and prevalence of LGT in evolution is deepening, there is a high demand for methods for detection of LGTs when reconstructing the evolutionary past of genes.

In this paper, we present highly efficient and practical algorithms for treereconciliation that simultaneously consider both duplications and LGTs. Weallow costs to be associated with duplications and LGTs and develop methods for finding reconciliations of minimal total cost between species trees andgene trees. Moreover, we provide an efficient algorithm for parametric treereconciliation—a computational problem analogous to parametric sequencealignment. Experimental results on synthetic data indicate that our methodsare robust with high specificity and sensitivity.

National Category
Bioinformatics and Systems Biology Computer Science
URN: urn:nbn:se:kth:diva-10970OAI: diva2:233572
QC 20100812Available from: 2009-09-01 Created: 2009-09-01 Last updated: 2012-05-02Bibliographically 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(231 kB)289 downloads
File information
File name FULLTEXT01.pdfFile size 231 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Tofigh, AliLagergren, Jens
By organisation
Computational Biology, CB
Bioinformatics and Systems BiologyComputer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 290 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

Total: 268 hits
ReferencesLink to record
Permanent link

Direct link