A program to compute the soft Robinson–Foulds distance between phylogenetic networks

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

Background

Over the past two decades, phylogenetic networks have been studied to model reticulate evolutionary events. The relationships among phylogenetic networks, phylogenetic trees and clusters serve as the basis for reconstruction and comparison of phylogenetic networks. To understand these relationships, two problems are raised: the tree containment problem, which asks whether a phylogenetic tree is displayed in a phylogenetic network, and the cluster containment problem, which asks whether a cluster is represented at a node in a phylogenetic network. Both the problems are NP-complete.

Results

A fast exponential-time algorithm for the cluster containment problem on arbitrary networks is developed and implemented in C. The resulting program is further extended into a computer program for fast computation of the Soft Robinson–Foulds distance between phylogenetic networks.

Conclusions

Two computer programs are developed for facilitating reconstruction and validation of phylogenetic network models in evolutionary and comparative genomics. Our simulation tests indicated that they are fast enough for use in practice. Additionally, the distribution of the Soft Robinson–Foulds distance between phylogenetic networks is demonstrated to be unlikely normal by our simulation data.

Electronic supplementary material

The online version of this article (doi:10.1186/s12864-017-3500-5) contains supplementary material, which is available to authorized users.

Related collections

Most cited references 23

Record: found
Abstract: found
Article: not found

Horizontal gene transfer, genome innovation and evolution.

J. Peter Gogarten, Jeffrey P Townsend (2005)

To what extent is the tree of life the best representation of the evolutionary history of microorganisms? Recent work has shown that, among sets of prokaryotic genomes in which most homologous genes show extremely low sequence divergence, gene content can vary enormously, implying that those genes that are variably present or absent are frequently horizontally transferred. Traditionally, successful horizontal gene transfer was assumed to provide a selective advantage to either the host or the gene itself, but could horizontally transferred genes be neutral or nearly neutral? We suggest that for many prokaryotes, the boundaries between species are fuzzy, and therefore the principles of population genetics must be broadened so that they can be applied to higher taxonomic categories.

0 comments Cited 349 times – based on 0 reviews      Review now

Bookmark

Record: found
Abstract: found
Article: not found

Pattern pluralism and the Tree of Life hypothesis.

W. Doolittle, Eric Bapteste (2007)

Darwin claimed that a unique inclusively hierarchical pattern of relationships between all organisms based on their similarities and differences [the Tree of Life (TOL)] was a fact of nature, for which evolution, and in particular a branching process of descent with modification, was the explanation. However, there is no independent evidence that the natural order is an inclusive hierarchy, and incorporation of prokaryotes into the TOL is especially problematic. The only data sets from which we might construct a universal hierarchy including prokaryotes, the sequences of genes, often disagree and can seldom be proven to agree. Hierarchical structure can always be imposed on or extracted from such data sets by algorithms designed to do so, but at its base the universal TOL rests on an unproven assumption about pattern that, given what we know about process, is unlikely to be broadly true. This is not to say that similarities and differences between organisms are not to be accounted for by evolutionary mechanisms, but descent with modification is only one of these mechanisms, and a single tree-like pattern is not the necessary (or expected) result of their collective operation. Pattern pluralism (the recognition that different evolutionary models and representations of relationships will be appropriate, and true, for different taxa or at different scales or for different purposes) is an attractive alternative to the quixotic pursuit of a single true TOL.

0 comments Cited 162 times – based on 0 reviews      Review now

Bookmark

Record: found
Abstract: found
Article: not found

Networks: expanding evolutionary thinking.

Leen Stougie, Carl Morrison, Leo van Iersel … (2013)

Networks allow the investigation of evolutionary relationships that do not fit a tree model. They are becoming a leading tool for describing the evolutionary relationships between organisms, given the comparative complexities among genomes. Copyright © 2013 Elsevier Ltd. All rights reserved.

0 comments Cited 74 times – based on 0 reviews      Review now

Bookmark

All references

Author and article information

Contributors

Bingxin Lu: bingxin@comp.nus.edu.sg

Louxin Zhang: matzlx@nus.edu.sg

Hon Wai Leong: leonghw@comp.nus.edu.sg

Conference

Journal ID (nlm-ta): BMC Genomics

Journal ID (iso-abbrev): BMC Genomics

Title: BMC Genomics

Publisher: BioMed Central (London )

ISSN (Electronic): 1471-2164

Publication date (Electronic): 14 March 2017

Publication date PMC-release: 14 March 2017

Publication date Collection: 2017

Volume: 18

Issue : Suppl 2 Issue sponsor : Publication of this supplement has not been supported by sponsorship. Information about the source of funding for publication charges can be found in the individual articles. The articles have undergone the journal's standard peer review process for supplements. The Supplement Editors declare that they have no competing interests.

Electronic Location Identifier: 111

Affiliations

[1 ]ISNI 0000 0001 2180 6431, GRID grid.4280.e, Department of Computer Science, , National University of Singapore, ; 13 Computing Drive, Singapore, 117417 Singapore

[2 ]ISNI 0000 0001 2180 6431, GRID grid.4280.e, Department of Mathematics, , National University of Singapore, ; 10 Lower Kent Ridge, Singapore, 119076 Singapore

Article

Publisher ID: 3500

DOI: 10.1186/s12864-017-3500-5

PMC ID: 5374702

PubMed ID: 28361712

SO-VID: 2aa59424-3912-4b76-b7d7-acb032a24fe0

License:

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License ( http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver ( http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.

Conference name: The Fifteenth Asia Pacific Bioinformatics Conference

Conference acronym: APBC 2017

Conference location: Shenzhen, China

Conference date: 16-18 January 2017

History

Custom metadata

ScienceOpen disciplines: Genetics

Keywords: phylogenetic network,cluster containment problem,tree containment problem,(soft) robinson–foulds distance,exponential-time algorithm

Data availability:

ScienceOpen disciplines: Genetics

Keywords: phylogenetic network, cluster containment problem, tree containment problem, (soft) robinson–foulds distance, exponential-time algorithm

A program to compute the soft Robinson–Foulds distance between phylogenetic networks

Read this article at

Abstract

Background

Results

Conclusions

Electronic supplementary material

Related collections

Genomic Prediction

Most cited references 23

Horizontal gene transfer, genome innovation and evolution.

Pattern pluralism and the Tree of Life hypothesis.

Networks: expanding evolutionary thinking.

Author and article information

Contributors

Conference

Affiliations

Article

History

Categories

Custom metadata

Comments

Comment on this article

Similar content 108

Cited by 4

Most referenced authors 228