Library for the Development and Use of Phylogenetic Network Methods
Core phylogenetic network data structures: Node, Edge, Branch, and Network classes.
This exception is raised when a network is malformed, or if a network operation fails.
This exception is raised when a Node operation fails.
This exception is raised when an Edge operation fails.
A lightweight, detached view of a single branch (edge) of a phylogenetic tree or network. Holds the branch length, inheritance probability, and the label of the parent node. Unlike :class:`Edge`, a ``Branch`` is not wired into a :class:`Network`; it is the value type handed to model nodes and other consumers that need branch parameters without the surrounding topology.
Get the length of the branch.
Get the inheritance probability (gamma) of the branch.
Get the label of the branch's parent node.
Initialize a Branch.
| Parameter | Type | Description |
|---|---|---|
| length | float, optional | Branch length. Defaults to None. |
| inheritance_probability | float, optional | Inheritance probability (gamma) for a reticulation branch. Defaults to None. |
| parent_id | str, optional | Label of the parent node. Defaults to None. |
Get the length of the branch.
Set the length of the branch. Negative values are rejected with a warning and leave the current value untouched.
| Parameter | Type | Description |
|---|---|---|
| value | float | The new branch length. |
Set the inheritance probability of the branch. Values outside [0, 1] are rejected with a warning and leave the current value untouched.
| Parameter | Type | Description |
|---|---|---|
| value | float | The new inheritance probability. |
Set the label of the branch's parent node.
| Parameter | Type | Description |
|---|---|---|
| value | str | The new parent node label. |
Return a string representation of the branch.
Return a string representation of the branch.
Node class that provides support for managing network constructs like reticulation nodes and other phylogenetic attributes.
Returns the name of the node
Initialize a node with a name, attribute mapping, and a hybrid flag.
| Parameter | Type | Description |
|---|---|---|
| name | str | A Node label. |
| is_reticulation | bool, optional | Flag that marks a node as a reticulation node if set to True. Defaults to False. |
| attr | dict[Any, Any], optional | Fill a mapping with any other user defined values. Defaults to a new empty dictionary. |
| seq | Union[DataSequence, None], optional | A data sequence wrapper. |
| t | Union[float, None], optional | A speciation time for this node. |
Retrieve the attribute mapping.
Set a node's attributes to a mapping of key labels to attribute values.
| Parameter | Type | Description |
|---|---|---|
| new_attr | dict[Union[str, Any], Any] | Attribute storage mapping. |
Get the speciation time for this node. Closer to 0 implies a time closer to the origin (the root). A larger time implies a time closer to the present (leaves).
Set the speciation time for this node. The arg 't' must be a non-negative number.
| Parameter | Type | Description |
|---|---|---|
| new_t | float | The new speciation/hybridization time for this node. |
NodeError: If the new time is negative.Create a string representation of a node.
Equality comparison for Node objects. Two nodes are equal if they have the same name (identity). Note: This is based on node identity, not biological distance.
| Parameter | Type | Description |
|---|---|---|
| other | Another object to compare against |
Hash function for Node objects. Uses the node name for hashing to maintain consistency with equality.
Create a description of a node and summarize its attributes.
Sets the name of the node to new_name.
| Parameter | Type | Description |
|---|---|---|
| new_name | str | A new string label for this node. |
Sets whether a node is a reticulation Node (or not).
| Parameter | Type | Description |
|---|---|---|
| new_is_retic | bool | Hybrid flag. True if this node is a reticulation node, false otherwise |
Retrieves whether a node is a reticulation Node (or not)
Put a key and value pair into the node attribute dictionary. If the key is already present, it will overwrite the old value.
| Parameter | Type | Description |
|---|---|---|
| key | Any | Attribute key. |
| value | Any | Attribute value for the key. |
If key is a key in the attributes mapping, then its value will be returned. Otherwise, returns None.
| Parameter | Type | Description |
|---|---|---|
| key | Any | A lookup key. |
Associate a data sequence with this node, if this node is a leaf in a network.
| Parameter | Type | Description |
|---|---|---|
| new_sequence | DataSequence | A data sequence wrapper. Grab from MSA object upon parsing. |
Gets the data sequence associated with this node.
NodeError: If no sequence record has been associated with this node.Duplicate this node by copying all data into a separate Node object. Useful for crafting copies of networks without having to deep copy.
Class for directed edges. Instead of being a wrapper for a "set" of member nodes, we can now think about an Edge as a wrapper for a tuple of member nodes (a, b), where now the direction is encoded in the ordering (where a is the source, and b the destination).
Get the source node of this edge.
Get the destination node of this edge.
An edge has a source (parent) and a destination (child). Edges in a phylogenetic context are *generally* directed. source -----> destination
| Parameter | Type | Description |
|---|---|---|
| source | Node | The parent node. |
| destination | Node | The child node. |
| length | float, optional | Branch length value. Defaults to None. |
| gamma | float, optional | Inheritance Probability, MUST be from [0,1]. Defaults to None. |
| weight | float, optional | Edge weight, can be any real number. Defaults to None. |
| tag | str, optional | A name tag for identifiability of hybrid edges should each have a gamma of 0.5. Defaults to None. |
ValueError: If @gamma is not a probabilistic value between 0 and 1 (inclusive, but if a hybrid edge pair has 0 and 1 then those hybrid edges may as well not exist)., EdgeError: If @length does not match the difference between @source.get_time() and @destination.get_time().Set the name/identifiability tag of this edge.
| Parameter | Type | Description |
|---|---|---|
| new_tag | str | a unique string identifier. |
Get the name/identifiability tag for this edge.
Set the inheritance probability of this edge. Only applicable to hybrid edges, but no warning will be raised if you attempt to set the probability of a non-hybrid edge.
| Parameter | Type | Description |
|---|---|---|
| gamma | float | A probability (between 0 and 1 inclusive). |
ValueError: If gamma is not between 0 and 1 inclusive.Gets the inheritance probability for this edge.
Craft an identical edge to this edge object, just in a new object. Useful in building subnetworks of a network that is in hand.
| Parameter | Type | Description |
|---|---|---|
| new_src | Node | None, optional | A new source node for this edge. |
| new_dest | Node | None, optional | A new destination node for this edge. |
Set the branch length of this edge. If enforce_times is True, then the branch length must be equivalent to the difference in times of the source and destination nodes. If warn_times is True, then a warning will be raised if the branch length is not equivalent to the difference in times of the source and destination nodes.
| Parameter | Type | Description |
|---|---|---|
| branch_length | float | The new branch length. |
| warn_times | bool, optional | If True, raises a warning if the branch length is not equivalent to the difference in times of the source and destination nodes. Defaults to False. |
| enforce_times | bool, optional | If True, raises an error if the branch length is not equivalent to the difference in times of the source and destination nodes. Defaults to False. |
EdgeError: If enforce_times is True and the branch length is not equivalent to the difference in times of the source and destination nodes. Warning: If warn_times is True and the branch length is not equivalent to the difference in times of the source and destination nodes.Get the branch length of this edge.
Set the weight of this edge.
| Parameter | Type | Description |
|---|---|---|
| new_weight | float | The new weight of this edge. |
Get the weight of this edge.
Get the names of the nodes in this edge.
Convert this edge to a Branch object for use in phylogenetic computations.
A directed (and potentially acyclic) graph of Nodes joined by Edges. An 'Edge' object is a wrapper class for a tuple of two nodes, (a, b), where a and b are Node objects, and the direction of the edge is from a to b (a is b's parent) -- thus (a, b) is NOT the same as (b, a). Notes and Allowances: 1) You may create cycles -- however we have provided a method to check if this graph object is acyclic. This method is internally called on methods that assume that a network has no cycles, so be mindful of the state of networks that are passed as arguments. 2) You may have multiple roots. Be mindful of whether this graph is connected and what root you wish to operate on. 3) You may end up with floater nodes/edges, ie this may be an unconnected network with multiple connected components. We will p...
Initialize a Network object. You may initialize with any combination of edges/nodes, or provide none at all. If you provide edges and no nodes, each node present in those edges *WILL* be added to the network.
| Parameter | Type | Description |
|---|---|---|
| edges | EdgeSet | set[Edge], optional | The edges of the network. Defaults to no edges. |
| nodes | NodeSet | set[Node], optional | The nodes of the network. Defaults to no nodes. |
| branch_length_unit | Explicit unit carried by edge lengths. Graph operations accept ``UNSPECIFIED``; biological calculations require a concrete unit. |
TypeError: If any provided edge is not an Edge object.Allows a simple pythonic "n in network" or "e in network" check.
| Parameter | Type | Description |
|---|---|---|
| obj | Node | Edge | A node or edge. |
TypeError: If @obj is neither a Node nor an Edge.Add any amount of nodes to this network. Accepts nodes as separate arguments, as lists, or as a mixture of both.
Ensure a node has a unique name that hasn't been used before/is not currently in use for this graph. May be used with a node that is or is not yet an element of V. The node will be added to V as a result of this function.
| Parameter | Type | Description |
|---|---|---|
| node | Node | None | Any node object. Defaults to None. |
Return the current value of the unique-id counter used by :meth:`add_uid_node`. Structural copies (see :meth:`Network.copy`) must carry this counter forward so that regenerated ``UID_*`` node names never collide with names already present in the graph.
Return the unit attached to this network's edge lengths.
Tag edge lengths with an explicit unit without rescaling them.
Set the unique-id counter used by :meth:`add_uid_node`.
| Parameter | Type | Description |
|---|---|---|
| value | int | The value to assign to the counter. |
Get all nodes in V.
Get the set E (in list form).
Access the blob storage with a key. CONSIDER REMOVAL OF THIS FUNCTION...
| Parameter | Type | Description |
|---|---|---|
| key | str | a string key to access the blob storage |
Add an item to the blob storage.
| Parameter | Type | Description |
|---|---|---|
| key | str | a string key to access the blob storage |
| item | Any | the object to store in the blob storage |
Check whether the graph has a node with a certain name. Strings must be exactly equal (same white space, capitalization, etc.)
| Parameter | Type | Description |
|---|---|---|
| name | str | the name to search for |
Get the in-degree of a node.
| Parameter | Type | Description |
|---|---|---|
| node | Node | A node in V |
Get the out-degree(number of edges where the given node is a parent) of a node in the graph.
| Parameter | Type | Description |
|---|---|---|
| node | Node | a node in V |
Get the in-edges of a node in V. The in-edges are the edges in E, where the given node is the child.
| Parameter | Type | Description |
|---|---|---|
| node | Node | a node in V |
Get the out-edges of a node in V. The out-edges are the edges in E, where the given node is the parent.
| Parameter | Type | Description |
|---|---|---|
| node | Node | a node in V |
Construct a Network object by passing in a newick string and parsing out the topology from there.
| Parameter | Type | Description |
|---|---|---|
| newick | str | An extended newick string. |
| branch_length_unit | Unit represented by parsed branch lengths. |
If edges is a list of Edges, then add each Edge to the list of edges. If edges is a singleton Edge then just add to the edge array. Note: Each edge that you attempt to add must be between two nodes that exist in the network. Otherwise, an error will be thrown.
| Parameter | Type | Description |
|---|---|---|
| edges | Edge | list[Edge] | a single edge, or multiple. |
NetworkError: if input edge/edges are malformed in any wayRemoves node from the list of nodes. Also prunes all edges from the graph that are connected to the node. Has no effect if node is not in this network.
| Parameter | Type | Description |
|---|---|---|
| node | Node | a Node obj |
Removes edge from the list of edges. Does not delete nodes with no edges Has no effect if 'edge' is not in the graph.
| Parameter | Type | Description |
|---|---|---|
| edge | Edge | list[Node] | an edge to remove from the graph |
| gamma | float | an inheritance probability from [0,1], if the edge is provided as a list of nodes, and there is an identifiability issue that needs resolving (ie, the edge that needs to be removed is a bubble edge). Optional. Defaults to None. |
NetworkError: If 'edge' is neither an Edge nor a [src, dest] pair.Rename a node and update *all* bookkeeping (NodeSet, EdgeSet, leaf/root sets). Node.__hash__ is name-based, so the node must be pulled out of every hash-keyed collection *before* the rename and put back *after*.
| Parameter | Type | Description |
|---|---|---|
| node | Node | a node in the graph |
| name | str | the new name for the node. |
Note, that in the event of bubbles, 2 edges will exist with the same source and destination. If this is possible, please supply the inheritance probability of the correct branch. If both edges are known to be identical (gamma = 0.5), then one will be chosen at random.
| Parameter | Type | Description |
|---|---|---|
| n1 | Node | parent node |
| n2 | Node | child node |
| gamma | float | inheritance probability. Optional. Defaults to None |
| tag | str | A name/identifiability tag for hybrid edges should both gammas be = .5. Optional. Defaults to None. |
Return the root of the Network. Phylogenetic networks only have one root, but for generality and practical use, multiple roots have been allowed. To get all roots, should multiple exist, call the function "roots". This function only returns 1 root.
NetworkError: If there are no roots in the network (cycle, or empty), or if there are multiple roots in the network.Return all root(s) of the Network. Phylogenetic networks typically have one root, but for generality and practical use, multiple roots have been allowed. Use ``root()`` to retrieve a single root.
Returns the set X (a subset of V), the set of all leaves (nodes with out-degree 0). Only returns the leaves that are connected/reachable from the root.
Returns a list of the parents of a node. There is no hard cap on the length of this array.
| Parameter | Type | Description |
|---|---|---|
| node | Node | any node in V. |
NetworkError: If the node is not in the graph.Returns a list of the children of a node. There is no hard cap on the length of this array.
| Parameter | Type | Description |
|---|---|---|
| node | Node | any node in V. |
NetworkError: If the node is not in the graph.Returns a dictionary of branches connected to the node.
| Parameter | Type | Description |
|---|---|---|
| node | Node | a node in the graph. |
All the various ways that the graph can be cleaned up and streamlined while not altering topology or results of algorithms. Algorithm Indeces: 0) Remove nodes that have in/out degree of 0 (floater nodes) 1) Remove a spurious root/root edge (root node with only one out edge) 2) Consolidate all chains of nodes with in/out degree of 1 into 1 edge. Default behavior is to run all three. To not run a certain routine, set the options list at the indeces listed above to False. Ie. To run the first and third algo, use [True, False, True].
| Parameter | Type | Description |
|---|---|---|
| options | list[bool], optional | A list of booleans that signal which algorithms to run. Defaults to [True, True, True]. |
Computes the Least Common Ancestor of a set of graph nodes.
| Parameter | Type | Description |
|---|---|---|
| set_of_nodes | set[Node] | set[str] | A set of Nodes, or node names. |
NetworkError: If any node in the set is not in the graph, or if elements are of an unexpected type.Compute the set of all leaf nodes that are descendants of the parameter node. Uses DFS to find paths to leaves.
| Parameter | Type | Description |
|---|---|---|
| node | Node | The node for which to compute leaf children. |
NetworkError: If node is not found in the graph.Returns 2 random edges such that there does not exist a directed path from one edge source node to the other edge source node.
| Parameter | Type | Description |
|---|---|---|
| rng | np.random.Generator | an rng object. |
Given a node in this graph, return the subgenome count.
| Parameter | Type | Description |
|---|---|---|
| n | Node | Any node in the graph. It is an error to input a node that is not in the graph. |
NetworkError: If the input node is not in the graph.Returns the set (as a list) of edges that are in the subgraph of a node.
| Parameter | Type | Description |
|---|---|---|
| n | Node | A node in a graph. |
NetworkError: If the input node is not in the graph.Returns the set (as a list) of edges that are in all paths from the root to this node. Useful in avoiding the creation of cycles when adding edges.
| Parameter | Type | Description |
|---|---|---|
| n | Node | A node in a graph. |
NetworkError: If the input node is not in the graph.Maps edges to their subgenome counts.
| Parameter | Type | Description |
|---|---|---|
| downstream_node | Node | None, optional | No edges will be included in the map that are in a subgraph of this node. Defaults to None. |
| delta | float, optional | Only include edges in the mapping that have subgenome counts <= delta. Defaults to math.inf. |
| start_node | Node | None, optional | Provide a node only if you don't want to start at the root. Defaults to None. |
NetworkError: If the graph has more than one root to start.Maps edges to their subgenome counts.
| Parameter | Type | Description |
|---|---|---|
| downstream_node | Node | None, optional | No edges will be included in the map that are in a subgraph of this node. Defaults to None. |
| delta | float, optional | Only include edges in the mapping that have subgenome counts <= delta. Defaults to math.inf. |
| start_node | Node | None, optional | Provide a node only if you don't want to start at the root. Defaults to None. |
NetworkError: If the graph has more than one root to start.Map each node in the graph to its set of leaf descendants
Generate the newick string of the network.
Checks if each of this graph's connected components is acyclic
General bfs-dfs routine, with the added utility of checking whether or not this graph is made up of multiple connected components.
| Parameter | Type | Description |
|---|---|---|
| start_node | Node | None, optional | Give a node to start the search from. Defaults to None, in which case the search will start at the root. |
| dfs | bool, optional | Flag that specifies whether to use bfs or dfs. Defaults to False (bfs), if true is passed, will run dfs. |
| is_connected | bool, optional | Flag that, if enabled, will check for the connected component status. Defaults to False (won't run). |
| accumulator | Callable[..., None] | None, optional | A function that takes the currently searched Node in the graph and does some sort of bookkeeping. |
| accumulated | Any | Any type of structure that stores the data given by the accumulator function. |
Make a copy of a subnetwork of this DAG, rooted at 'retic_node', with unique node names.
| Parameter | Type | Description |
|---|---|---|
| retic_node | Node | A node in this network that is a reticulation node |
Copy this network into a new network object, also with new node and edge objects.
Convert this network to a NetworkX graph object.
Check if this network is topologically isomorphic to another network. Two networks are isomorphic if they have the same topology, regardless of node labels or branch lengths. This method calls the GraphUtils.is_isomorphic function.
| Parameter | Type | Description |
|---|---|---|
| other | Network | The other network to compare against. |
Computes the rooted triplet distance between two networks. This distance measure compares the topological relationships between all triplets of leaves in both networks. For each triplet of leaves {x, y, z}, the pair sharing the deepest MRCA are identified as siblings, producing a canonical encoding. The distance is the normalized symmetric difference of these triplet sets.
| Parameter | Type | Description |
|---|---|---|
| other | Network | The other network to compare against. |
Collect all nodes in the subtree rooted at the given node.
| Parameter | Type | Description |
|---|---|---|
| node | Node | The root of the subtree. |
Get the distance from the root to the given node, measured in edge count (hop count) via BFS.
| Parameter | Type | Description |
|---|---|---|
| node | Node | A node in this network. |
Compute a topological order of nodes in an acyclic network.
NetworkError: If the network contains a directed cycle and no valid topological order exists.Compute distance from root to a given node.
| Parameter | Type | Description |
|---|---|---|
| node | Node | The target node |
| use_time | bool | If True, use branch lengths/times. If False, use edge count. |
NetworkError: If node is not in the network or no path to root existsSet time attributes for all nodes based on their distance from root. Uses cumulative branch lengths from root. Useful for enabling biologically meaningful node comparisons. The root node is assigned time 0.0 and each descendant's time is the sum of branch lengths along the BFS path from the root.
Set time attributes for all nodes based on their edge count from root. This provides biologically meaningful comparison when actual times are not available. Edge counts are converted to time values for comparison purposes. The root node is assigned time 0.0 and each descendant's time equals the number of edges on the BFS path from the root.
A subclass of a Network, that is a binary tree that results from the transformation of a standard network into a Multilabeled Species Tree.
Initializes a MUL object.
| Parameter | Type | Description |
|---|---|---|
| gene_map | dict[str, list[str]] | A mapping from gene names to a set of gene copy names. |
| rng | np.random.Generator | A numpy random number generator. |
Creates a (MU)lti-(L)abeled Species Tree from a network
| Parameter | Type | Description |
|---|---|---|
| net | Network | A Network |
NetworkError: If the network is malformed with regards to ploidy