phylox.rearrangement.heuristics.green_line_heuristic

A module containing the Green Line heuristic and its random version. The Green Line heuristic is a heuristic to find a sequence of rSPR or tail moves between two phylogenetic networks. The algorithms referred to in the comments are from the R Janssen’s PhD thesis, “Rearranging Phylogenetic Networks”, 2021.

Classes

HeuristicDistanceMixin()

A class containing the Green Line heuristic and its random version.
phylox.rearrangement.heuristics.green_line_heuristic.GL_Case1_Tail(N, Np, up, isom_N_Np, isom_Np_N, randomNodes=False, seed=None)

An implementation of Algorithm 6. Finds a sequence of tail moves that makes it possible to add the lowest reticulation up to the down-closed isomrophism.

Parameters:

  • N – a phylogenetic network.

  • Np – a phylogenetic network.

  • up – a lowest reticulation node of Np above the isomorphism.

  • isom_N_Np – a dictionary, containing a partial (down-closed) isomorphism map from N to Np. The inverse of isom_Np_N.

  • isom_Np_N – a dictionary, containing a partial (down-closed) isomorphism map from Np to N. The inverse of isom_N_Np.

  • randomNodes – a boolean value, determining whether the random version of this lemma is used.

  • seed – a seed for the random number generator.

Returns:

a list of tail moves in N, a list of tail moves in Np, a node of N, a node of Np. After performing the lists of moves on the networks, the nodes can be added to the isomorphism. Returns false if the networks are not isomorphic with 2 leaves and 1 reticulation.

phylox.rearrangement.heuristics.green_line_heuristic.GL_Case3(N, Np, up, isom_N_Np, isom_Np_N, randomNodes=False, seed=None)

An implementation of Algorithm 3. Finds a sequence of tail moves that makes it possible to add the lowest tree node up to the down-closed isomrophism.

Parameters:

  • N – a phylogenetic network.

  • Np – a phylogenetic network.

  • up – a lowest tree node of Np above the isomorphism.

  • isom_N_Np – a dictionary, containing a partial (down-closed) isomorphism map from N to Np. The inverse of isom_Np_N.

  • isom_Np_N – a dictionary, containing a partial (down-closed) isomorphism map from Np to N. The inverse of isom_N_Np.

  • randomNodes – a boolean value, determining whether the random version of this lemma is used.

  • seed – a seed for the random number generator.

Returns:

a list of tail moves in N, a list of tail moves in Np, a node of N, a node of Np. After performing the lists of moves on the networks, the nodes can be added to the isomorphism.

class phylox.rearrangement.heuristics.green_line_heuristic.HeuristicDistanceMixin

Bases: object

A class containing the Green Line heuristic and its random version. Meant to be inherited by the RearrangementProblem class.

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.