Minimizing the deep coalescence cost
| Autor: | Dawid Dąbkowski, Pawel Tabaszewski, Paweł Górecki |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
0106 biological sciences
0301 basic medicine Computer science Binary number 010603 evolutionary biology 01 natural sciences Biochemistry 03 medical and health sciences Databases Genetic Animals Quantitative Biology::Populations and Evolution Molecular Biology Phylogeny Coalescence (physics) Binary tree Models Genetic Phylogenetic tree Spacetime Gene tree Computational Biology Quantitative Biology::Genomics Computer Science Applications Exponential function Dynamic programming 030104 developmental biology Metagenomics ComputingMethodologies_GENERAL Algorithm Algorithms |
| Zdroj: | Journal of Bioinformatics and Computational Biology. 16:1840021 |
| ISSN: | 1757-6334 0219-7200 |
| Popis: | Metagenomic studies identify the species present in an environmental sample usually by using procedures that match molecular sequences, e.g. genes, with the species taxonomy. Here, we first formulate the problem of gene-species matching in the parsimony framework using binary phylogenetic gene and species trees under the deep coalescence cost and the assumption that each gene is paired uniquely with one species. In particular, we solve the problem in the cases when one of the trees is a caterpillar. Next, we propose a dynamic programming algorithm, which solves the problem exactly, however, its time and space complexity is exponential. Next, we generalize the problem to include non-binary trees and show the solution for caterpillar trees. We then propose time and space-efficient heuristic algorithms for solving the gene-species matching problem for any input trees. Finally, we present the results of computational experiments on simulated and empirical datasets consisting of binary tree pairs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|