A cubic-time algorithm for computing the trinet distance between level-1 networks

DOI10.1016/J.IPL.2017.03.002MaRDI QIDQ522967zbMATH OpenOpenAlexFDO

Authors James Oldman, Vincent Moulton, Taoyang Wu

Publication date 20 April 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.05097, https://ueaeprints.uea.ac.uk/id/eprint/62948/1/Trinet_IPL_rev.pdf

zbMATH Keywords

algorithmsphylogenetic treephylogenetic networktrinetRobinson-Foulds metric

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms (68W40) Software, source code, etc. for problems pertaining to biology (92-04)

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.

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

Cites work

• Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
• Comparison of phylogenetic trees
• Computing the rooted triplet distance between galled trees by counting triangles
• Encoding and constructing 1-nested phylogenetic networks with trinets
• New common ancestor problems in trees and directed acyclic graphs
• Optimal algorithms for comparing trees with labeled leaves
• ReCombinatorics. The algorithmics of ancestral recombination graphs and explicit phylogenetic networks. With contributions from Charles H. Langley, Yun S. Song and Yufeng Wu
• Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations
• Trinets encode tree-child and level-2 phylogenetic networks

Cited in

(4)

• TriLoNet
• Fast algorithms for computing the tripartition-based distance between phylogenetic networks
• Biological Networks: Comparison, Conservation, and Evolutionary Trees
• Algorithms and Computation

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)