Neighborhoods of trees in circular orderings

Bastkowski, Sarah, Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435, Spillner, Andreas and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001 (2015) Neighborhoods of trees in circular orderings. Bulletin of Mathematical Biology, 77 (1). pp. 46-70. ISSN 0092-8240

Preview

PDF (moves-2014) - Accepted Version Download (458kB) | Preview

Abstract

In phylogenetics, a common strategy used to construct an evolutionary tree for a set of species X is to search in the space of all such trees for one that optimizes some given score function (such as the minimum evolution, parsimony or likelihood score). As this can be computationally intensive, it was recently proposed to restrict such searches to the set of all those trees that are compatible with some circular ordering of the set X. To inform the design of efficient algorithms to perform such searches, it is therefore of interest to find bounds for the number of trees compatible with a fixed ordering in the neighborhood of a tree that is determined by certain tree operations commonly used to search for trees: the nearest neighbor interchange (nni), the subtree prune and regraft (spr) and the tree bisection and reconnection (tbr) operations. We show that the size of such a neighborhood of a binary tree associated with the nni operation is independent of the tree’s topology, but that this is not the case for the spr and tbr operations. We also give tight upper and lower bounds for the size of the neighborhood of a binary tree for the spr and tbr operations and characterize those trees for which these bounds are attained.

Item Type:	Article
Additional Information:	An erratum to the article has been published, correcting the spelling of the first author's name. DOI: 10.1007/s11538-015-0071-y The correct spelling is given in this entry.
Uncontrolled Keywords:	phylogenetic tree,nearest neighbor interchange,subtree prune and regraft,tree bisection and reconnection ,neighbornet,circular ordering
Faculty \ School:	Faculty of Science > School of Computing Sciences Faculty of Science
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:	02 Jan 2015 12:42
Last Modified:	13 Jun 2023 08:29
URI:	https://ueaeprints.uea.ac.uk/id/eprint/51235
DOI:	10.1007/s11538-014-0049-1

Downloads

Actions (login required)

View Item