A cubic-time algorithm for computing the trinet distance between level-1 networks
From MaRDI portal
Publication:522967
DOI10.1016/J.IPL.2017.03.002zbMATH Open1407.92096arXiv1703.05097OpenAlexW2597301589MaRDI QIDQ522967FDOQ522967
Authors: James Oldman, Vincent Moulton, Taoyang Wu 
Publication date: 20 April 2017
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: In evolutionary biology, phylogenetic networks are constructed to represent the evolution of species in which reticulate events are thought to have occurred, such as recombination and hybridization. It is therefore useful to have efficiently computable metrics with which to systematically compare such networks. Through developing an optimal algorithm to enumerate all trinets displayed by a level-1 network (a type of network that is slightly more general than an evolutionary tree), here we propose a cubic-time algorithm to compute the trinet distance between two level-1 networks. Employing simulations, we also present a comparison between the trinet metric and the so-called Robinson-Foulds phylogenetic network metric restricted to level-1 networks. The algorithms described in this paper have been implemented in JAVA and are freely available at https://www.uea.ac.uk/computing/TriLoNet.
Full work available at URL: https://arxiv.org/abs/1703.05097
Recommendations
- Net and prune: a linear time algorithm for Euclidean distance problems
- Net and prune: a linear time algorithm for Euclidean distance problems
- Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree
- Cache oblivious algorithms for computing the triplet distance between trees
- Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees
- Approximation algorithm for the distance-3 independent set problem on cubic graphs
- Fast algorithms for the rooted triplet distance between caterpillars
- A Quadratic Time Algorithm for the Minmax Length Triangulation
- An oblivious shortest-path routing algorithm for fully connected cubic networks
Problems related to evolution (92D15) Analysis of algorithms (68W40) Software, source code, etc. for problems pertaining to biology (92-04)
Cites Work
- Comparison of phylogenetic trees
- Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
- Optimal algorithms for comparing trees with labeled leaves
- Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations
- ReCombinatorics. The algorithmics of ancestral recombination graphs and explicit phylogenetic networks. With contributions from Charles H. Langley, Yun S. Song and Yufeng Wu
- Trinets encode tree-child and level-2 phylogenetic networks
- New common ancestor problems in trees and directed acyclic graphs
- Encoding and constructing 1-nested phylogenetic networks with trinets
- Computing the rooted triplet distance between galled trees by counting triangles
Cited In (4)
This page was built for publication: A cubic-time algorithm for computing the trinet distance between level-1 networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q522967)
