phylox.rearrangement.exact_distance.base.ExactMethodsMixin

class phylox.rearrangement.exact_distance.base.ExactMethodsMixin

Bases: object

__init__()

Methods

__init__()

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.
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.