Branch-and-Bound Approach for Parsimonious Inference of a Species Tree From a Set of Gene Family Trees

Jean-Philippe Doyon 1, * Cedric Chauve 2
* Corresponding author
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We describe a Branch-and-Bound algorithm for computing a parsimonious species tree given a set of gene family trees. Our algorithm can compute a parsimonious species tree for three cost measures: number of gene duplications, number of gene losses, and both combined. Moreover, to cope with intrinsic limitations of Branch-and-Bound algorithms for species trees inference regarding the number of taxa that can be considered, our algorithm can naturally take into account predefined relationships between sets of taxa. We test our algorithm on a dataset of eukaryotic gene families spanning 29 taxa.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00448481
Contributor : Jean-Philippe Doyon <>
Submitted on : Monday, May 3, 2010 - 12:28:09 PM
Last modification on : Wednesday, June 26, 2019 - 4:28:03 PM
Long-term archiving on: Thursday, December 1, 2016 - 1:20:11 AM

File

branchAndBound.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00448481, version 2

Collections

Citation

Jean-Philippe Doyon, Cedric Chauve. Branch-and-Bound Approach for Parsimonious Inference of a Species Tree From a Set of Gene Family Trees. RR-10001, 2010, pp.18. ⟨lirmm-00448481v2⟩

Share

Metrics

Record views

796

Files downloads

540