Computing Galled Networks from Real Data

Daniel Huson 1 Regula Rupp 1 Vincent Berry 2 Philippe Gambette 3, * Christophe Paul 3
* Corresponding author
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Developing methods for computing phylogenetic networks from biological data is an important problem posed by molecular evolution and much work is currently being undertaken in this area. Although promising approaches exist, there are no tools available that biologists could easily and routinely use to compute rooted phylogenetic networks on real datasets containing tens or hundreds of taxa. Biologists are interested in clades, that is, groups of monophyletic taxa, and these are usually represented by clusters in a rooted phylogenetic tree. The problem of computing an optimal rooted phylogenetic network from a set of clusters, is hard, in general. Indeed, even the problem of just determining whether a given network contains a given cluster is hard. Hence, some researchers have focused on topologically restricted classes of networks, such as galled trees and level-k networks, that are more tractable, but have the practical draw-back that a given set of clusters will usually not possess such a representation. In this paper we argue that galled networks (a generalization of galled trees) provide a good trade-off between level of generality and tractability. Any set of clusters can be represented by some galled network and the question whether a cluster is contained in such a network is easy to solve. Although the computation of an optimal galled network involves solving instances of two different NPcomplete problems, in practice our algorithm solves this problem exactly on large datasets containing hundreds of taxa and many reticulations in seconds, as illustrated by a dataset containing 279 prokaryotes. We provide a fast, robust and easy-to-use implementation of this work in version 2.0 of our tree-handling software Dendroscope.
Document type :
Conference papers
ISMB/ECCB'09: 17th Annual Conference on Intelligent Systems for Molecular Biology & 8th European Conference on Computational Biology, Jun 2009, France. Oxford Journals, 25(12), pp.i85-i93, 2009, Bioinformatics. 〈http://www.iscb.org/ismbeccb2009/〉. 〈10.1093/bioinformatics/btp217〉
Liste complète des métadonnées

Cited literature [31 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00368545
Contributor : Philippe Gambette <>
Submitted on : Saturday, June 20, 2009 - 3:23:08 PM
Last modification on : Thursday, October 26, 2017 - 1:44:08 PM
Document(s) archivé(s) le : Wednesday, September 22, 2010 - 12:45:54 PM

File

2009HusonRuppBerryGambettePaul...
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Daniel Huson, Regula Rupp, Vincent Berry, Philippe Gambette, Christophe Paul. Computing Galled Networks from Real Data. ISMB/ECCB'09: 17th Annual Conference on Intelligent Systems for Molecular Biology & 8th European Conference on Computational Biology, Jun 2009, France. Oxford Journals, 25(12), pp.i85-i93, 2009, Bioinformatics. 〈http://www.iscb.org/ismbeccb2009/〉. 〈10.1093/bioinformatics/btp217〉. 〈lirmm-00368545v2〉

Share

Metrics

Record views

336

Files downloads

530