Structural properties of distance-bounded phylogenetic reconciliation

Cyriac Antony, Alessio Martino, Blerina Sinaimeri · 2026

Read Structural properties of distance-bounded phylogenetic reconciliation by Cyriac Antony, Alessio Martino, Blerina Sinaimeri (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22193.txt.

Introduction

Cyriac Antony, Alessio Martino, and Blerina Sinaimeri study a hard puzzle from the study of how species evolve. Their 2026 preprint looks at ways to map a parasite family tree onto a host family tree. Events such as shared splits, copies, host jumps, and losses link the two trees.

The hard part is to find the best map when time facts are not full. The team focus on maps where host jumps stay within a fixed short range. They probe the shape and cost of such maps. Their results guide those who build tools for this task.

Catalog record

CREATORCyriac Antony, Alessio Martino, Blerina Sinaimeri
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-22193

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Structural properties of distance-bounded phylogenetic reconciliation Cyriac Antony, Alessio Martino, Blerina Sinaimeri Abstract Phylogenetic reconciliation seeks to explain host–symbiont co-evolution by mapping parasite trees onto host trees through events such as cospeciation, duplication, host switching, and loss. Finding an optimal reconciliation that ensures time feasibility is computationally hard when timing information is incomplete, and the complexity remains open when host switches are restricted by a fixed maximum distance d d . While the case d = 2 d=2 is known to be polynomial, larger values are unresolved. In this paper, we study the cases d = 3 d=3 and d = 4 d=4 . We show that although arbitrarily large cycles may occur, it suffices to check only bounded-size cycles (we provide a complete list), provided the reconciliation satisfies acyclicity (i.e., time-feasibility) in a stronger sense. These results do not resolve the general complexity, but highlight structural properties that advance the understanding of distance-bounded reconciliations. Keywords: phylogenetic reconciliation, cophylogeny, host-switch distance, time-feasibility. 1 Introduction Understanding how parasites (or more generally symbionts) have co-evolved with their hosts is a fundamental problem which has applications that range from evolutionary biology to public health, for example in uncovering the origins of new infectious diseases [ 7 , 9 , 12 ] . The increasing availability of DNA sequence data has only amplified the importance of such analyses. One of the main approaches to study host–symbiont co-evolution is through cophylogeny , which derive joint evolutionary scenarios for both hosts and parasites, typically represented as phylogenetic trees computed from sequence data. In this framework, the interaction between host and symbiont lineages is captured by a reconciliation a mapping of the parasite tree onto the host tree (see, e.g., [ 4 , 10 , 6 , 14 ] ). This mapping allows the identification of four macro evolutionary events: (a) cospeciation , where parasite divergence coincides with host divergence; (b) duplication , where the parasite diverges independently of the host; (c) host switching , where a parasite colonizes a new host species unrelated to host divergence; and (d) loss , which can capture cases where the host speciates but the parasite lineage follows only one of the new host species. Reconciliations can be constructed in a parsimonious framework: one assigns a cost to each of the four types of events and then seeks to minimize the total cost (computed in an additive way). If timing information (i.e., the order in which the speciation events occurred in the host phylogeny for incomparable vertices) is not known (or is considered as not sufficiently reliable to be used), as is often the case, the problem is NP-hard [ 11 , 16 ] . A way to deal with this is either to rely on heuristics [ 5 ] (that is, on approaches that are not guaranteed to be optimal) or to settle for solutions that may be biologically unfeasible, that is for solutions where some of the switches induce a contradictory time ordering for the internal vertices of the host tree [ 1 , 14 , 6 , 8 , 18 ] . It is worth noting that while finding an optimal time-feasible reconciliation is computationally hard, checking whether a given reconciliation is time-feasible can be done in polynomial time by constructing an auxiliary directed graph encoding the temporal constraints and verifying the absence of cycles (see e.g. [ 14 , 18 ] ). Because timing information is often unavailable, one alternative is to enrich the reconciliation framework with other biological signals. An important example is the distance of host switches, defined as the distance in the host tree between the donor and recipient species of a switch. This measure reflects the idea that symbionts more readily colonize closely related hosts, while long-distance switches may require substantial adaptive changes [ 17 , 13 ] . Distance has been integrated into parsimony-based frameworks in different ways. For instance, [ 6 ] restrict switches to occur only within a given bounded distance in the host tree, whereas in [ 2 ] the cost of a switch increases with its distance, so that longer switches are penalized but not forbidden. In both cases, however, there is no guarantee that the resulting optimal reconciliations are time-feasible. It therefore remains an open problem to determine whether fixing the maximum allowed distance d (when d is not part of the input) could yield optimal, time-feasible reconciliations in polynomial time. For the special case d=2 , the problem is solvable in polynomial time since all reconciliations are acyclic as pointed out in [ 15 ] ; but as the authors emphasize, this result does not extend directly to larger values of d . In this paper, we address the next open cases, namely d=3 and d=4 . We show that although arbitrarily large cycles may arise in a reconciliation, it is nevertheless sufficient to focus on cycles of bounded size (we provide a complete list of such short cycles), provided the reconciliation satisfies acyclicity in a stronger sense. This makes it possible to check for cycles locally, which can have algorithmic consequences. While these results do not directly resolve the algorithmic complexity of the problem, they shed new light on its structural properties and provide useful tools for further studies. 2 Preliminaries In this section we provide some definitions and basic results that will be used throughout the paper. For a directed graph G , we denote by V(G) and E(G) respectively the set of nodes and the set of arcs of G . The out-neighbors of a node v are called its children. We consider ordered rooted trees in which arcs are directed away from the root. For a tree T , we denote by L(T) the set of leaf nodes, i.e. those nodes without children, and denote by r_{T} the root of T ; the non-leaf nodes are called the internal nodes of T . A rooted full binary tree is a rooted tree in which every internal node has two children. A phylogenetic tree is a rooted full binary tree. We denote by p(w) the parent of a node w . If there exists a path from a node v to a node w , the node w is called a descendant of v , and v is called an ancestor of w ; if moreover v\neq w , we say that w is a proper descendant of v , and that v is a proper ancestor of w . If neither w is an ancestor of v nor v is an ancestor of w , we say that the two nodes are incomparable , and denote this as v\not\sim w . If a node u is a child of a child of v , then u is said to a grandchild of v . If a node u and a node v have the same parent, then u and v are siblings . If the parent of a node u and the parent of a node v are siblings, then u and v are said to be cousins . We denote by \textsf{LCA}(v,w) the lowest common ancestor of two nodes v and w . The subtree of a tree T rooted at

Read the complete text