Introduction

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. AVAILABILITY AND IMPLEMENTATION: The C++ source code for the algorithms and simulations described in the article are available at http://www-ens.iro.umontreal.ca/~lafonman/software.php. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Publications

  1. Polytomy refinement for the correction of dubious duplications in gene trees.
    Cite this
    Lafond M, Chauve C, Dondi R, El-Mabrouk N, 2014-09-01 - Bioinformatics (Oxford, England)

Credits

  1. Manuel Lafond
    Developer

    Department of Computer Science, Université de Montréal, Italy

  2. Cedric Chauve
    Developer

    Department of Computer Science, Université de Montréal, Italy

  3. Riccardo Dondi
    Developer

    Department of Computer Science, Université de Montréal, Italy

  4. Nadia El-Mabrouk
    Investigator

    Department of Computer Science, Université de Montréal, Italy

Community Ratings

UsabilityEfficiencyReliabilityRated By
0 user
Sign in to rate
Summary
AccessionBT003408
Tool TypeApplication
Category
PlatformsLinux/Unix
TechnologiesC++
User InterfaceTerminal Command Line
Download Count0
Country/RegionItaly
Submitted ByNadia El-Mabrouk