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

Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435, Oldman, James and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001 (2017) A cubic-time algorithm for computing the trinet distance between level-1 networks. Information Processing Letters, 123. 36–41. ISSN 0020-0190

Preview

PDF (Accepted manuscript) - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (332kB) | Preview

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)

Item Type:	Article
Uncontrolled Keywords:	phylogenetic tree,phylogenetic network,level-1 network,trinet,robinson-foulds metric
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	Pure Connector
Date Deposited:	14 Mar 2017 01:41
Last Modified:	14 Jun 2023 12:54
URI:	https://ueaeprints.uea.ac.uk/id/eprint/62948
DOI:	10.1016/j.ipl.2017.03.002

Downloads

Actions (login required)

View Item