Abstract | ||
---|---|---|
Motivation: Large-scale methods for inferring gene trees are error-prone. Correcting gene trees for weakly supported features often results in non-binary trees, i.e. trees with polytomies, thus raising the natural question of refining such polytomies into binary trees. A feature pointing toward potential errors in gene trees are duplications that are not supported by the presence of multiple gene copies. Results: We introduce the problem of refining polytomies in a gene tree while minimizing the number of created non-apparent duplications in the resulting tree. We show that this problem can be described as a graph-theoretical optimization problem. We provide a bounded heuristic with guaranteed optimality for well-characterized instances. We apply our algorithm to a set of ray-finned fish gene trees from the Ensembl database to illustrate its ability to correct dubious duplications. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1093/bioinformatics/btu463 | BIOINFORMATICS |
Keywords | Field | DocType |
ecology,microbiology,neuroscience,medicine,health,publishing,biology,plant biology,genetics,oncology,anaesthesiology,physiology,cell biology | Heuristic,Polytomy,Source code,Ensembl,Computer science,Algorithm,Binary tree,Theoretical computer science,Software,Bioinformatics,Optimization problem,Bounded function | Journal |
Volume | Issue | ISSN |
30 | 17 | 1367-4803 |
Citations | PageRank | References |
2 | 0.37 | 23 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manuel Lafond | 1 | 3 | 1.41 |
cedric chauve | 2 | 429 | 41.81 |
Riccardo Dondi | 3 | 89 | 18.42 |
Nadia El-Mabrouk | 4 | 512 | 41.88 |