Inferring Duplications and Lateral Gene Transfers: An Algorithm for Parametric Tree Reconciliation
(English)Manuscript (preprint) (Other academic)
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.
Bioinformatics and Systems Biology Computer Science
IdentifiersURN: urn:nbn:se:kth:diva-10970OAI: oai:DiVA.org:kth-10970DiVA: diva2:233572
QC 201008122009-09-012009-09-012012-05-02Bibliographically approved