phylox.cherrypicking.tree_child_sequences

Functions for finding tree child sequences in a network.

Based on “Linear Time Algorithm for Tree-Child network Containment” by Remie Janssen and Yukihiro Murakami (2020)

Functions

`check_cherry_picking_sequence`(N, ...[, labels])	Check if a cherry picking sequence is valid for a network.
`find_tree_child_sequence`(network[, labels])	Find a tree child sequence for a network.
`tree_child_network_contains`(N, M[, labels])	Check if a tree child network N contains another network M.

phylox.cherrypicking.tree_child_sequences.find_tree_child_sequence(network, labels=False)

Find a tree child sequence for a network. If the network is orchard but not tree-child, this function may produce a cherry-picking sequence that reduces the network to a single edge, but that is not a tree-child sequence.

Parameters:

network (phylox.DiNetwork) – The network to find a tree child sequence for.
labels (bool) – Whether to return the tree child sequence as a list of labels instead of a list of nodes.

Returns:

The tree child sequence.

Return type:

list

Example:

>>> from phylox import DiNetwork
>>> N = DiNetwork(
...     edges=[(-1, 0), (0, 1), (0, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (4, 6)],
...     labels=[(5, "A"), (6, "B")],
... )
>>> try:
...     find_tree_child_sequence(N, labels=True)
... except ValueError:
...     exception_raised = True
>>> exception_raised
True

>>> N = DiNetwork(
...     edges=[(-1, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 6)],
...     labels=[(5, "A"), (6, "B")],
... )
>>> TC_sequence = find_tree_child_sequence(N, labels=True)
>>> TC_sequence == [("B", "A"), ("B", "A"), ("B", "A")] or TC_sequence == [("A", "B"), ("B", "A"), ("B", "A")]
True

phylox.cherrypicking.tree_child_sequences.check_cherry_picking_sequence(N, cherry_picking_sequence, labels=False)

Check if a cherry picking sequence is valid for a network.

Parameters:

N (phylox.DiNetwork) – The network to check the cherry picking sequence for.
cherry_picking_sequence (list) – The cherry picking sequence to check.
labels (bool) – Whether the cherry picking sequence is given as a list of labels instead of a list of nodes.

Returns:

True if the cherry picking sequence reduces the network to a single edge, False otherwise.

Return type:

bool

Example:

>>> from phylox import DiNetwork
>>> N = DiNetwork(
...     edges=[(-1, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 4)],
...     labels=[(3, "A"), (4, "B")],
... )
>>> check_cherry_picking_sequence(N, [("B", "A"), ("B", "A")], labels=True)
True

phylox.cherrypicking.tree_child_sequences.tree_child_network_contains(N, M, labels=False)

Check if a tree child network N contains another network M.

Parameters:

N (phylox.DiNetwork) – The network to check for containment.
M (phylox.DiNetwork) – The network to check for.
labels (bool) – Whether to return the tree child sequence as a list of labels instead of a list of nodes.

Returns:

True if N contains M, False otherwise.

Return type:

bool

Example:

>>> from phylox import DiNetwork
>>> N = DiNetwork(
...     edges=[(-1, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 4)],
...     labels=[(3, "A"), (4, "B")],
... )
>>> M = DiNetwork(
...     edges=[(-1, 0), (0, 1), (0, 2)],
...     labels=[(1, "A"), (2, "B")],
... )
>>> tree_child_network_contains(N, M, labels=True)
True