Soft Tree Containment on Tree-Child Networks

Reference implementations for the paper Soft Tree Containment on Tree-Child Networks (arXiv identifier to be added).

A phylogenetic network N softly displays a tree T when some switching of N (one retained in-edge per reticulation) displays a tree whose clusters contain every cluster of T. The paper shows that deciding this is polynomial on single-labelled tree-child networks at every reticulation in-degree, for the asymmetric notion (only the polytomies of T may be refined) and for the symmetric notion, and that it is NP-hard once T may omit taxa of N, though decidable in |N|^O(e) time for e missing taxa.

Contents

Module	Paper	What it does
softtc/network.py	Section 2	networks and trees as networkx digraphs, switchings, displayed trees, clusters, the linear cluster-containment test
softtc/encoding.py	Sections 2 and 5	the DFS-canonical order, tree components, principal paths and leaf intervals (table T1), the cluster–component table (T2), the rows of the lineage-taxon hypersequence
softtc/carve.py	Section 6, Lemma 41, Algorithm 4	the per-cluster computation: candidate hosts, reach thresholds, feasible hosts and their boxes, the intervals H_{r,p}, the unary and binary projections
softtc/case1.py	Section 4, Algorithm 1	binary T, tree-child N of any degrees: row alignment, O(|N| + |T|)
softtc/case2.py	Section 5, Algorithm 3	non-binary T, binary N: clauses from the intervals, 2-SAT
softtc/case3.py	Section 6, Algorithm 5	non-binary T, N of any degrees: projections, arc-consistency, deepest-parent witness
softtc/symmetric.py	Section 7	the symmetric notion: compatibility boxes, generalized arc-consistency
softtc/missing_taxa.py	Section 8, Theorem 58	T on a subset of the taxa: leaf deletion, branching at deficient vertices
softtc/twosat.py		2-SAT by strongly connected components
softtc/oracle.py		brute force over all switchings, used by the tests
softtc/generators.py		random tree-child networks and trees
tests/test_softtc.py		the examples of the paper and random instances against brute force

Every decider returns a switching that certifies a positive answer, and every positive answer is checked on the displayed tree before it is returned.

Usage

import random
from softtc import soft_displays, symmetric_soft_displays, case3, generators
from softtc.network import network, tree

# the network of Figure 1 of the paper: root -> s, s -> g1, g2, g1 -> m, r, g2 -> d, r, m -> a, b, r -> c
N, root = network([("rho", "s"), ("s", "g1"), ("s", "g2"), ("g1", "m"), ("g1", "r"),
                   ("g2", "d"), ("g2", "r"), ("m", "a"), ("m", "b"), ("r", "c")],
                  {"a": "a", "b": "b", "c": "c", "d": "d"})
T, _ = tree((("a", "b"), "c", "d"))        # the tree ((a,b),c,d)
soft_displays(N, root, T)                  # True: a switching refines the polytomy
symmetric_soft_displays(N, root, T)        # True

random.seed(1)
N, root = generators.random_network(list("abcdefgh"), k=3, max_in_degree=4)
T = generators.random_displayed_tree(N, root, contract_prob=0.5)
accept, f = case3.decide(N, root, T)       # f is the certified switching

soft_displays dispatches to Case 1, 2 or 3 by the shape of the input, and to the missing-taxa procedure when T is on a proper subset of the taxa of N; the case modules can also be called directly. Networks are networkx.DiGraphs whose root has out-degree one and whose leaves carry a taxon attribute; see softtc/network.py for the conventions and network/tree for two builders.

Requirements and tests

Python 3.9 or later and networkx (pip install -r requirements.txt). Run the tests with pytest or python tests/test_softtc.py.

Citing and license

Please cite the paper; a BibTeX entry will be added with the arXiv identifier. The code is released under the MIT License (see LICENSE).