pylogeny.landscape module¶

Encapsulate a phylogenetic tree space. A phylogenetic landscape or tree space refers to the entire combinatorial space comprising all possible phylogenetic tree topologies for a set of n taxa. The landscape of n taxa can be defined as consisting of a finite set T of tree topologies. Tree topologies can be associated with a fitness function f(t_i) describing their fit. This forms a discrete solution search space and finite graph (T, E) = G. E(G) refers to the neighborhood relation on T(G). Edges in this graph are bidirectional and represent transformation from one tree topology to another by a tree rearrangement operator. An edge between t_i and t_j would be notated as e_{ij} in E(G).

class pylogeny.landscape.graph(gr=None, defWeight=0.0)[source]¶

Bases: object

Define an empty graph object.

__init__(gr=None, defWeight=0.0)[source]¶

Instantiate a graph. Default edge weights are 0.

Parameters:	gr (a `networkx.Graph` object) – a networkx graph object, if already exists. defWeight (a floating point number) – the default edge weight of weights

clearEdgeWeights()[source]¶: Set all edge weights to the default edge weight.

getCenter()[source]¶: Get the centre of the graph.

getCliqueNumber()[source]¶

Get the clique number of the graph.

Returns:	an integer

getCliques()[source]¶: Get the cliques present in the graph.

getCliquesOfNode(i)[source]¶: Get the clique that a node corresponds to.

getComponentOfNode(i)[source]¶: Get the graph component of a given node.

getComponents()[source]¶: Get the connected components in the graph.

getDegreeFor(i)[source]¶

Return in- and out-degree for node named i.

Parameters:	i (a string) – a node name
Returns:	an integer

getDiameter()[source]¶: Acquire the diameter of the graph.

getEdge(i, j)[source]¶

Get the data associated with an edge (including weight).

Parameters:	i (a string) – a node name j (a string) – a node name
Returns:	an edge (and associated data)

getEdges()[source]¶

Get all edges (as defined for NetworkX graphs). Recommended to use an iterator for large graphs.

Returns:	a list of edges (and associated data)

getEdgesFor(i)[source]¶

Get all edges associated with a certain node.

Parameters:	i (a string) – a node name
Returns:	a list of edges (and associated data) for all neighbors

getMST()[source]¶: Acquire the minimum spanning tree for the graph.

getNeighborsFor(i)[source]¶

Get a list of all node names neighbor to a node.

Parameters:	i (a string) – a node name
Returns:	a list of strings (node names)

getNode(i)[source]¶

Get a single node by name.

Parameters:	i (a string) – a node name:
Returns:	a dictionary (with node information)

getNodeNames()[source]¶

Return the names of nodes in the graph.

Returns:	a list of strings

getNodes()[source]¶

Get all node values. Recommended to use an iterator for large graphs (iterNodes()).

Returns:	a list of node values (whatever is associated with nodes)

getNumCliques()[source]¶

Get the number of cliques found in the graph.

Returns:	an integer

getNumComponents()[source]¶

Get the number of components of the graph.

Returns:	an integer

getShortestPath(nodA, nodB)[source]¶: Get the shortest path between two nodes.

getShortestPathLength(nodA, nodB)[source]¶: Get the shortest path length between two nodes.

getSize()[source]¶

Return the number of nodes in the graph.

Returns:	an integer

hasPath(nodA, nodB)[source]¶: See if a path exists between two nodes.

isEdge(i, j)[source]¶

See if an edge exists between two nodes.

Parameters:	i (a string) – a node name j (a string) – a node name
Returns:	a boolean

iterNodes()[source]¶

Iterate over all node keys.

Returns:	a generator of node keys

setDefaultWeight(w)[source]¶

Set the default weight of edges (weight of edges if not overridden).

Parameters:	w (a floating point) – a weight

class pylogeny.landscape.landscape(ali, starting_tree=None, root=True, operator='SPR')[source]¶

Bases: pylogeny.landscape.graph, pylogeny.tree.treeSet

Defines an entire phylogenetic tree space.

__init__(ali, starting_tree=None, root=True, operator='SPR')[source]¶

Initialize the landscape.

Parameters:

ali (an alignment.alignment object) – an alignment
starting_tree (a tree.tree object) – an optional tree object to start with
root (a boolean) – whether or not to compute an approximate maximum likelihood tree (FastTree) or start the landscape with a given starting tree.
operator (a string) – a string that describes what operator the landscape is mostly comprised of.

addTree(tr, score=True, check=True, newick=None, struct=None)[source]¶

Add a tree to the landscape. Will return its index.

Parameters:	tr (a `tree.tree` object) – a tree score (a boolean) – defaults to True, whether to score this tree or not
Returns:	the index of the tree

addTreeByNewick(newick, score=True, check=True, struct=None)[source]¶

Add tree to the landscape by Newick string. Will return index.

Parameters:	newick (a string) – a Newick string score (a boolean) – defaults to True, whether to score this tree or not
Returns:	the index of the tree

exploreRandomTree(i, type=1)[source]¶

Acquire a single neighbor to a tree in the landscape by performing a random rearrangement of type SPR (by default), NNI, or TBR – this is done by performing a rearrangement on a random branch in the topology. Rearrangement type is provided as a rearrangement module type definition of form, for example, TYPE_SPR, TYPE_NNI, etc.

Parameters:	i – a tree index type – the type of rearrangement (e.g., TYPE_SPR, TYPE_NNI)
Returns:	the new tree index or None in case of failure

exploreTree(i, type=1)[source]¶

Get all neighbors to a tree named i in the landscape using a respective rearrangement operator as defined in the rearrangement module. Rearrangement type is provided as a rearrangement module type definition of form, for example, TYPE_SPR, TYPE_NNI, etc. By default, this is TYPE_SPR.

Parameters:	i – a tree index type – the type of rearrangement (e.g., TYPE_SPR, TYPE_NNI)
Returns:	a list of neighbors as tree names (usually integers)

findTree(newick)[source]¶

Find a tree by Newick string, taking into account branch lengths. Returns the index of this tree in the landscape. Warning: naively performs a sequential search.

Parameters:	newick (a string) – a Newick string
Returns:	a tree name (usually an integer index) or None if not found

findTreeTopology(newick)[source]¶

Find a tree by topology, not taking into account branch lengths.

Parameters:	newick (a string) – a Newick string
Returns:	a tree name (usually an integer index) or None if not found

findTreeTopologyByStructure(struct)[source]¶

Find a tree by topology, not taking into account branch lengths, given the topology.

Parameters:	struct (a string) – a Newick string without branch lengths (a “structure”)
Returns:	a tree name (usually an integer index) or None if not found

getAlignment()[source]¶

Acquire the alignment object associated with this space.

Returns:	an `alignment.alignment` object

getAllPathsOfBestImprovement()[source]¶

Return all paths of best improvement as a dictionary.

Returns:	a dictionary of tree name to paths (lists of tree names)

getBestImprovement(i)[source]¶

For a tree in the landscape, investigate neighbors to find a tree that leads to the best improvement of fitness function score on the basis of likelihood.

Parameters:	i – a tree name (usually an integer)
Returns:	a tree name (usually an integer) or None if no better tree

getBipartitionFoundInTreeByIndex(tr, brind, topol=None)[source]¶

Given a tree node and a branch index, return the associated bipartition.

Parameters:	tr – a tree name brind – a branch index in that tree, a la post-order traversal
Returns:	a `tree.bipartition` object

getGlobalOptimum()[source]¶

Get the global optimum of the current space.

Returns:	a tree name (usually an integer)

getLocalOptima()[source]¶

Get all trees in the landscape that can be labelled as a local optimum.

Returns:	a list of tree names (usually integers)

getLocks()[source]¶

Get all restrictions (locks which cannot be violated on splits).

Returns:	a list of `tree.bipartition` objects

getNumberTaxa()[source]¶

Return the number of different taxa present in any respective tree in the landscape.

Returns:	an integer

getPathOfBestImprovement(i)[source]¶

For a tree in the landscape, investigate neighbors iteratively until a best path of score improvement is found on basis of likelihood.

Parameters:	i – a tree name (usually an integer)
Returns:	a list of tree names (usually integers)

getPossibleNumberRootedTrees()[source]¶

Assuming all of the trees in the space are rooted, return the maximum possible number of unrooted trees that can possibly be generated for the number of taxa of trees in the landscape.

Returns:	an integer

getPossibleNumberUnrootedTrees()[source]¶

Assuming all of the trees in the space are unrooted, return the maximum possible number of unrooted trees that can possibly be generated for the number of taxa of trees in the landscape.

Returns:	an integer

getRoot()[source]¶

Returns the index to the root (starting) tree of the space.

Returns:	an integer

getRootNode()[source]¶

Returns the root (starting) tree of the space in its node form.

Returns:	a dictionary (with node information)

getRootTree()[source]¶

Acquire the first tree that was placed in this space.

Returns:	a `tree.tree` object

getTree(i)[source]¶

Get the object for a tree by its name.

Parameters:	i – a tree name (usually an integer)
Returns:	a `tree.tree` object

getVertex(i)[source]¶

Acquire a vertex object from the landscape; this is a high-level representation of a tree in the landscape with additional functionality. Object created upon invocation of this function.

Parameters:	i – a tree name (usually an integer)
Returns:	a `vertex` object

indexOf(tr)[source]¶

Acquire the index/name in this landscape of a tree object. Returns -1 if not found. Warning: naively performs a sequential search.

Parameters:	tr (a `tree.tree` object) – a tree
Returns:	a tree name (usually an integer index) or -1 if not found

isLocalOptimum(i)[source]¶

Determine if a tree is a local optimum. This means it has the following properties:

Possesses a likelihood score.

Local neighborhood completely enumerated (and scored).

None of its neighbors is a better improvement.

Returns:	a boolean

isViolating(i)[source]¶

Determine if a tree is violating any locks intrinsic to the landscape. Will also return False if the tree (name) is not present in the landscape.

Parameters:	i – a tree name (usually an integer)

iterAllPathsOfBestImprovement()[source]¶

Return an iterator for all paths of best improvement.

Returns:	a generator of paths (lists of tree names)

lockBranchFoundInTree(tr, br)[source]¶

Given a tree node and a branch object, add a given bipartition to the bipartition lock list. Returns bipartition if locked.

Parameters:	tr – a tree name br (a `base.treeBranch` object) – a branch in that tree
Returns:	a `tree.bipartition` object that has been locked or None

lockBranchFoundInTreeByIndex(tr, brind)[source]¶

Given a tree node and a branch index, add an associated bipartition to the bipartition lock list. Returns the bipartition if locked.

Parameters:	tr – a tree name brind – a branch index
Returns:	a `tree.bipartition` object if it has been locked

removeTree(tree)[source]¶

Remove a tree from the landscape by object.

Parameters:	tree (a `tree.tree` object) – a tree that exists in the landscape
Returns:	a boolean (success or failure)

removeTreeByIndex(i)[source]¶

Remove a tree from the landscape by index.

Parameters:	i – a tree name (usually an integer)
Returns:	a boolean (success or failure)

setAlignment(ali)[source]¶

Set the alignment present in this landscape. WARNING; will not modify existing scores.

Parameters:	ali (an `alignment.alignment` object) – an alignment

setOperator(op)[source]¶

Set the operator assigned to this landscape.

Parameters:	op (a string) – an operator (string description)

toProperNewickTreeSet()[source]¶

Convert this landscape into an unorganized set of trees where taxa names are transformed to their original form (i.e. not transformed to a state friendly for the Phylip format).

Returns:	a `tree.treeSet` object

toTreeSet()[source]¶

Convert this landscape into an unorganized set of trees.

Returns:	a `tree.treeSet` object

toggleLock(lock)[source]¶

Add a biparition to the list of locked bipartitions if not present; otherwise, remove it. Return status of lock.

Parameters:	lock (a `tree.bipartition` object) – a bipartition that cannot be violated
Returns:	a boolean (on or off)

class pylogeny.landscape.vertex(obj, ls)[source]¶

Bases: object

Encapsulate a single vertex in the landscape and add convenient functionality to alias parent landscape functions.

__init__(obj, ls)[source]¶: Initialize this vertex.

approximatePossibleNumNeighbors()[source]¶

Approximate the possible number of neighbors to this vertex by considering the type of tree rearrangement operator. Returns LS_NOT_DEFINED if the operator is not known yet.

Returns:	an integer

getBestImprovement()[source]¶: Alias function for function of same name in parent landscape.

getBipartitionScores()[source]¶: Get all corresponding bipartition vectors of SPR scores.

getBipartitions()[source]¶

Get all bipartitions for this vertex.

Returns:	a list of `tree.bipartition` objects

getDegree()[source]¶

Get the degree of this tree in the graph.

Returns:	an integer

getDict()[source]¶

Get the dictionary object (key-value pairs) associated with this tree as it is in the NetworkX graph.

Returns:	a dictionary

getIndex()[source]¶

Get the index of this tree in the space.

Returns:	a tree name (usually an integer)

getNeighbors()[source]¶

Get any neighbors to this tree in the landscape.

Returns:	a list of tree names (usually integers)

getNeighborsOfBipartition(bi)[source]¶: Get corresponding neighbors of a bipartition in this vertex’s tree.

getNeighborsOfBranch(br)[source]¶: Get corresponding neighbors of a branch in this vertex’s tree.

getNewick()[source]¶

Get the Newick string of this tree.

Returns:	a string

getObject()[source]¶

Get the dictionary object (key-value pairs) associated with this tree as it is in the NetworkX graph.

Returns:	a dictionary

getOrigin()[source]¶

Get the origin of this tree (how it was acquired).

Returns:	a string

getPathOfBestImprovement()[source]¶: Alias function for function of same name in parent landscape.

getProperNewick()[source]¶: Get the proper Newick string for a tree. :returns: A string.

getScore()[source]¶

Get (any) score(s) associated with this tree.

Returns:	a tuple of floating point values (scores)

getTree()[source]¶

Get the tree object associated with this tree.

Returns:	a `tree.tree` object

isBestImprovement()[source]¶

Check to see if this vertex is a best move for another node.

Returns:	a boolean

isExplored()[source]¶

See if this tree has had all possible rearrangements performed.

Returns:	a boolean

isFailed()[source]¶

Determine if any errors are associated with this node.

Returns:	a boolean

isLocalOptimum()[source]¶

Determine if this tree is an optimum.

Returns:	a boolean

isViolating()[source]¶: Alias function for function of same name in parent landscape.

iterBipartitions()[source]¶: Return a generator to iterate over all bipartitions for this vertex.

scoreLikelihood()[source]¶

Acquire the log-likelihood for this vertex.

Returns:	the log-likelihood score

setExplored(exp)[source]¶

Override the “explored” flag of this node in the landscape.

Parameters:	exp – a boolean

pylogeny.landscape module¶

Previous topic

Next topic

This Page

Navigation

pylogeny.landscape module¶

Previous topic

Next topic

This Page

Quick search

Navigation