phylox.rearrangement.rearrangementproblem.RearrangementProblem

class phylox.rearrangement.rearrangementproblem.RearrangementProblem(network1, network2, move_type)

Bases: ExactMethodsMixin, HeuristicDistanceMixin

A rearrangement problem is a tuple (N1, N2, M) where N1 and N2 are phylogenetic networks and M is a move type.

Parameters:

  • network1 – a phylogenetic network phylox.DiNetwork.

  • network2 – a phylogenetic network phylox.DiNetwork.

  • move_type – a move type phylox.rearrangement.move.MoveType.

Example:

>>> from phylox import DiNetwork
>>> from phylox.rearrangement.rearrangementproblem import RearrangementProblem
>>> from phylox.rearrangement.move import MoveType, Move
>>> network1 = DiNetwork(
...     edges=[(0,1),(1,2),(1,3)],
...     labels=[(2, "A"), (3, "B")],
... )
>>> network2 = DiNetwork(
...     edges=[(0,1),(1,2),(1,3),(2,3),(2,4),(3,5)],
...     labels=[(4, "A"), (5, "B")],
... )
>>> problem = RearrangementProblem(network1, network2, MoveType.ALL)
>>> problem.check_solution([
...     Move(
...         move_type=MoveType.VPLU,
...         start_edge=(1,2),
...         end_edge=(1,3),
...         network = network1,
...     ),
... ])
True
__init__(network1, network2, move_type)

Methods

__init__(network1, network2, move_type)

check_green_line_requirements()

check_solution(seq_moves[, isomorphism])

Checks if a sequence of moves solves the rearrangement problem.

heuristic_green_line()

An implementation of Algorithm 4 and its tail move counterpart.

heuristic_green_line_random

solve_depth_first([max_time, show_bounds])

An implementation of Algorithm 1 from R.

solve_depth_first_bounded([max_depth, stop_time])

A subroutine of Algorithm 1 of R.
check_solution(seq_moves, isomorphism=None)

Checks if a sequence of moves solves the rearrangement problem.

Parameters:

  • seq_moves – a sequence of moves phylox.rearrangement.move.Move.

  • isomorphism – a partial isomorphism between the networks.

Returns:

true if the sequence of moves solves the rearrangement problem, false otherwise.

Example:

>>> from phylox import DiNetwork
>>> from phylox.rearrangement.rearrangementproblem import RearrangementProblem
>>> from phylox.rearrangement.move import MoveType, Move
>>> network1 = DiNetwork(
...     edges=[(0,1),(1,2),(1,3)],
...     labels=[(2, "A"), (3, "B")],
... )
>>> network2 = DiNetwork(
...     edges=[(0,1),(1,2),(1,3),(2,3),(2,4),(3,5)],
...     labels=[(4, "A"), (5, "B")],
... )
>>> problem = RearrangementProblem(network1, network2, MoveType.ALL)
>>> problem.check_solution([
...     Move(
...         move_type=MoveType.VPLU,
...         start_edge=(1,2),
...         end_edge=(1,3),
...         network = network1,
...     ),
... ])
True
heuristic_green_line()

An implementation of Algorithm 4 and its tail move counterpart. Finds a sequence of tail/rSPR moves from network1 to network2 by building a down-closed isomorphism. Assumes the networks have the same leaf set, the same number of reticulations, are both binary, and all labels are unique.

Returns:

A list of tail/rSPR moves from network1 to network2. Returns False if such a sequence does not exist.

heuristic_green_line_random(seed=None)

An implementation of Algorithm 5 and its tail move counterpart. Finds a sequence of tail/rSPR moves from network1 to network2 by randomly building a down-closed isomorphism.

Returns:

A list of tail/rSPR moves from network1 to network2. Returns False if such a sequence does not exist.

solve_depth_first(max_time=False, show_bounds=True)

An implementation of Algorithm 1 from R. Janssen’s PhD thesis. Uses an iterated Depth First Search to simulate a Breath First Search.

Parameters:

  • max_time – a float, a time limit for the function in seconds. If False, no time limit is used, and the function continues until it finds a sequence.

  • show_bounds – a boolean parameter, if True the current lower bounds are printed to the terminal, used for debugging.

Returns:

a shortest sequence of moves between the networks if it is found within the time limit, otherwise it returns an integer: a lower bound for the length of the shortest sequence between the networks.

Example:

>>> from phylox.rearrangement.rearrangementproblem import RearrangementProblem
solve_depth_first_bounded(max_depth=0, stop_time=False)

A subroutine of Algorithm 1 of R. Janssen’s PhD thesis. A depth-bounded Depth First Search used to simulate a Breath First Search.

Parameters:

  • max_depth – a integer, the maximum depth for the search tree.

  • stop_time – a float, a time limit for the function in clock time. If False, no time limit is used, and the function continues until it finds a sequence.

Returns:

a shortest sequence of at most max_depth moves between the networks if it is found before the stop_time, otherwise it returns an False.