Heading in the right direction? Using head moves to traverse phylogenetic network space

Research output: Contribution to journalArticleScientificpeer-review

4 Downloads (Pure)

Abstract

Head moves are a type of rearrangement moves for phylogenetic net-works. They have primarily been studied as part of other types of moves, such as rSPR moves. Here, we study head moves as a type of moves on themselves. We show that the tiers (k > 0) of phylogenetic network space are connected by local head moves. Then, we show tail moves and head moves are closely related: sequences of tail moves can be converted into sequences of head moves and vice versa, changing the length by at most a constant factor. Because the tiers of network space are connected by rSPR moves, this gives a second proof of the connectivity of these tiers. Furthermore, we show that these tiers have small diameter by reproving the connectivity a third time. As the head move neighbourhood is small in general, this makes head moves a good candidate for local search heuristics. Finally, we prove that finding the shortest sequence of head moves between two networks is NP-hard.

Original languageEnglish
Pages (from-to)263-310
Number of pages48
JournalJournal of Graph Algorithms and Applications
Volume25
Issue number1
DOIs
Publication statusPublished - 2021

Keywords

  • Phylogenetics
  • Rearrangement
  • Graph theory
  • NP-completeness
  • Connectedness
  • Phylogenetic networks

Fingerprint Dive into the research topics of 'Heading in the right direction? Using head moves to traverse phylogenetic network space'. Together they form a unique fingerprint.

Cite this