phylox.cherrypicking.combining_networks.HybridizationProblem

class phylox.cherrypicking.combining_networks.HybridizationProblem(list_of_networks=None, newick_strings=True)

Bases: object

A class to represent a hybridization problem. I.e. a set of phylogenetic networks that need to be combined into a single phylogenetic network. The networks all need to have a unique root with out-degree 1.

Parameters:

list_of_networks – a list of phylogenetic networks, each given as a phylox.DiNetwork.
newick_strings – if True, the input trees are given as newick strings, otherwise as phylox.DiNetworks.

__init__(list_of_networks=None, newick_strings=True)

Methods

`CPHeuristic`
`CPHeuristicLengths`
`CPHeuristicStorePairs`
`CPSBound`
`Find_All_Pairs`()	Finds the set of reducible pairs in all trees Returns a dictionary with reducible pairs as keys, and the trees they reduce as values.
`Height_Pair`(pair, trees)	Returns the average height of a pair in a set of trees The pair must be reducible in each tree in 'trees'
`Improve_Sequence`(CPS, reduced_trees[, progress])	Improves a sequence 'CPS' for the input trees by removing elements and checking whether the new sequence still reduces all trees.
`Reduce_Pair_In_All`(pair[, reducible_pairs])	Reduces the given pair in all networks in the problem.
`Reduce_Trivial_Pairs`(candidate_leaves)	Reduces the trivial pairs in the current set of networks.
`Reduce_Trivial_Pairs_Lengths`(...)	Reduces the trivial pairs in the current set of networks.
`Reduce_Trivial_Pairs_Store_Pairs`(...)	Reduces the trivial pairs in the current set of networks.
`Trivial_Pair_With`(l)	Returns all trivial pairs involving the leaf l as first element of the pair.
`Update_Heights`(current_heights, reducible_pairs)	Returns an updated dictionary of heights of the reducible pairs
`Update_Reducible_Pairs`(reducible_pairs, ...)	Returns the updated dictionary of reducible pairs in all trees after a reduction (with the trees they reduce as values) we only need to update for the trees that got reduced: 'new_red_treed'
`__init__`([list_of_networks, newick_strings])

CPSBound(repeats=1, progress=False, track=False, lengths=False, time_limit=None, seed=None)

Finds a cherry-picking sequence for the input networks, and updates the best sequence found so far.

The method simply keeps picking (random) cherries until all networks are reduced to a single leaf. If lengths is True, the method picks the lowest cherry in each step (CPHeuristicLenths). If track is True, the method keeps track of the reducible pairs in each step, and reduces the most common pair (CPHeuristicStorePairs). Otherwise, the method simply picks a random cherry in each step (CPHeuristic).

Parameters:

repeats – the number of times to run the algorithm.
progress – if True, print progress information.
track – if True, keep track of reducible pairs and reduce the most common pair.
lengths – if True, pick the lowest cherry in each step.
time_limit – if given, the algorithm stops after this many seconds.

Returns:

the best sequence found so far.

Example:

>>> from phylox import DiNetwork
>>> from phylox.cherrypicking.combining_networks import HybridizationProblem
>>> network1 = DiNetwork(
...     edges=[(0,1),(1,2),(1,3),(2,3),(2,4),(3,5)],
...     labels=[(4, "A"), (5, "B")],
... )
>>> network2 = DiNetwork(
...     edges=[(0,1),(1,2),(1,3),(2,3),(2,4),(3,5)],
...     labels=[(4, "A"), (5, "B")],
... )
>>> problem = HybridizationProblem(
...     list_of_networks=[network1, network2],
...     newick_strings=False,
... )
>>> sequence = problem.CPSBound()
>>> sequence == [('B', 'A'), ('B', 'A')] or sequence == [('B', 'A'), ('A', 'B')]
True

Update_Heights(current_heights, reducible_pairs): Returns an updated dictionary of heights of the reducible pairs

Height_Pair(pair, trees): Returns the average height of a pair in a set of trees The pair must be reducible in each tree in ‘trees’

Find_All_Pairs(): Finds the set of reducible pairs in all trees Returns a dictionary with reducible pairs as keys, and the trees they reduce as values.

Update_Reducible_Pairs(reducible_pairs, new_red_trees): Returns the updated dictionary of reducible pairs in all trees after a reduction (with the trees they reduce as values) we only need to update for the trees that got reduced: ‘new_red_treed’

Reduce_Pair_In_All(pair, reducible_pairs={})

Reduces the given pair in all networks in the problem. Returns the set of networks that were reduced.

Note:

This method changes the set of networks in the problem, so it should only be called in a copy of the problem.

Parameters:

pair – a pair of leaves.
reducible_pairs – a dictionary of reducible pairs and the networks in which they are reducible, as returned by Find_All_Pairs.

Reduce_Trivial_Pairs(candidate_leaves)

Reduces the trivial pairs in the current set of networks. Runs efficiently by giving a set of leaves ‘candidate_leaves’ that may be involved in trivial pairs. This set must be given; after a reduction of the pair (a,b) only using the leaves a and b works. Returns the reduced pairs and the sets of networks that were reduced.

Note:: This method changes the set of networks in the problem, so it should only be called in a copy of the problem.

Reduce_Trivial_Pairs_Store_Pairs(candidate_leaves, reducible_pairs)

Reduces the trivial pairs in the current set of networks. Runs efficiently by giving a set of leaves ‘candidate_leaves’ that may be involved in trivial pairs. This set must be given; after a reduction of the pair (a,b) only using the leaves a and b works. Returns the reduced pairs and the sets of networks that were reduced, also updates the reducible pairs.

This method is similar to Reduce_Trivial_Pairs, but it uses and updates the dictionary of reducible pairs to reduce the trivial pairs.

Note:: This method changes the set of networks in the problem, so it should only be called in a copy of the problem.

Reduce_Trivial_Pairs_Lengths(candidate_leaves, reducible_pairs)

Reduces the trivial pairs in the current set of networks. Runs efficiently by giving a set of leaves ‘candidate_leaves’ that may be involved in trivial pairs. This set must be given; after a reduction of the pair (a,b) only using the leaves a and b works. Returns the reduced pairs and the sets of networks that were reduced, also updates the reducible pairs and their heights.

This method is similar to Reduce_Trivial_Pairs, but it uses and updates the dictionary of reducible pairs to reduce the trivial pairs. It also keeps track of the heights of the reduced pairs.

Note:: This method changes the set of networks in the problem, so it should only be called in a copy of the problem.

Trivial_Pair_With(l): Returns all trivial pairs involving the leaf l as first element of the pair.

Improve_Sequence(CPS, reduced_trees, progress=False): Improves a sequence ‘CPS’ for the input trees by removing elements and checking whether the new sequence still reduces all trees. Returns this improved sequence and the corresponding sets of reduced trees for each pair.