Heading in the right direction? Using head moves to traverse phylogenetic network space
| Autor: | Remie Janssen |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Heading (navigation)
Traverse General Computer Science Computer science Head (linguistics) Rearrangement Topology Connectedness Theoretical Computer Science Phylogenetic networks FOS: Mathematics Mathematics - Combinatorics Local search (optimization) Quantitative Biology - Populations and Evolution Sequence business.industry Populations and Evolution (q-bio.PE) Neighbourhood (graph theory) Phylogenetic network NP-completeness Computer Science Applications Phylogenetics Graph theory Computational Theory and Mathematics FOS: Biological sciences Combinatorics (math.CO) Geometry and Topology business Versa |
| Zdroj: | Journal of Graph Algorithms and Applications, 25(1) |
| ISSN: | 1526-1719 |
| DOI: | 10.7155/jgaa.00559 |
| Popis: | Head moves are a type of rearrangement moves for phylogenetic networks. They have mostly been studied as part of more encompassing 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 to 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 in general small, 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. 39 pages, 27 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|