Runs the InPhyNet algorithm on the given distance matrix and constraint networks where the entries in namelist correspond to indices in D.

Arguments

• use_heuristic::Bool (default=true): whether or not InPhyNet should use a heuristic to determine whether a given merge will result in a future conflict. Setting this value to false will sharply improve runtimes but will almost always lead to algorithm failure due to merging conflicts if the input data are not very close to ground truth (even with the pairwise fallback algorithm inphynetpairwise).
• refuse_pairwise::Bool (default=false): whether InPhyNet should refuse to run the pairwise fallback algorithm inphynetpairwise if the main algorithm fails. Can lead to algorithm failure if set to true - only change if you know what you're doing.

calculateAGID(Ns::AbstractVector{HybridNetwork})

Calculates the Average Gene tree Internode Distance for all pairs of taxa across all networks in Ns.

Returns

1. AGID matrix
2. names of taxa corresponding to rows/columns in the AGID matrix

Heuristic for determining whether the set of networks ns are compatible.

Converts the tree/network net into a SimpleGraph to leverage already implemented pathfinding algorithms.

Arguments

• includeminoredges (default=true): if true, the entire network is translated to a graph. Otherwise, only tree-like edges (other than those in alwaysinclude) are retained.
• alwaysinclude (default=nothing): edges that should always be included in the graph, regardless of the value of includeminoredges
• withweights (default=false): return a set of weights corresponding to branch lengths as well
• removeredundantedgecost (default=false): if true, finds all the nodes that would be removed via removeredundantedges! and sets their weights in W to 0

calculateAGIC(Ns::AbstractVector{HybridNetwork})

Calculates the Average Gene tree Internode Counts for all pairs of taxa across all networks in Ns. If allow_missing_pairs is false, an error will be thrown if there are pairs of taxa that never appear in Ns together. Otherwise, entries for taxa that never appear together will be set to default_missing_value.

Returns

1. AGIC matrix
2. names of taxa corresponding to rows/columns in the AGID matrix

calculateAGID(Ns::AbstractVector{HybridNetwork})

Calculates the Average Gene tree Internode Distance for all pairs of taxa across all networks in Ns.

Returns

1. AGID matrix
2. names of taxa corresponding to rows/columns in the AGID matrix

Calculates pairwise_metric on each pair of networks in Ns. Called by calculateAGIC and calculateAGID. pairwise_metric must be a function that takes a HybridNetwork as its first positional input, must accept the named argument namelist, and must return a 2-Tuple of (A, B), where A is the pairwise metric applied to all pairs of taxa in the supplied network, and B is the namelist used or generated by the fxn.

Slightly adjusted implementation of the decomposition algorithm from SATe-I that takes a maximum and a minimum subset size.

Checks validity of a single input constraint networks. Checks include:

1. All nodes have exactly 3 edges except the root (unless the network is a single taxa)
2. Reticulations do not lead directly into other reticulations

Checks validity of input constraints. So far, the only check is to make sure that all nodes have exactly 3 edges except for the root.

Deals with all the overhead of connecting two nodes with an edge. Returns the edge used to connect the nodes.

Helper function for when an edge (notinpath_edge) appears on but not within a merge path. Finds and returns: 1. Whether the edge should be logged with direction "to" or "from" 2. Whether the edge should be associated with subnetedgei or subnetedgej

Helper function that finds a path in net from nodei to nodej. If that path has 2 or more reticulations in it, the cost to include a hybrid in the path is incrementally increased until only 1 reticulation is in the path.

findoptQ(D::Matrix{Float64}, idxpairs::Vector{Tuple{<:Integer, <:Integer}})

Finds the minimizer (i, j) among all pairs (i, j) in idxpairs for Q, a matrix computed from D.

findsiblingpairs(net::HybridNetwork)

Finds sibling pairings for all the leaves in a single network. These pairs are valid for net but may not be valid when the other constraint networks are also considered. Returns a vector of tuples of nodes corresponding to siblings.

findvalidpairs(constraints::Vector{HybridNetwork}, constraint_sibling_pairs, namelist::AbstractVector{<:AbstractString})

Finds all valid sibling pairs among the constraint networks.

Helper function to remove redundant edges (e.g. A –> (internal node) –> (internal node)) that arise from one case of the function mergeconstraintnodes!.

Redundant nodes in this case will always have only two edges while not being the root.

Helper function used at one point in mergeconstraintnodes!. Gets all of the descendants of node that do not have any children and are not in path

Gets all the leaf nodes underneath edge edge.

Finds a branch in tre that, when pruned on, splits the tree roughly in half.

Helper function - returns true if the node node is connected directly to the root of net, or if the path connecting node to net's root is multiple redundant edges (e.g. returns true for A in the net: "((((((A))))), (B,C));")

Runs the InPhyNet algorithm on the given distance matrix and constraint networks where the entries in namelist correspond to indices in D.

Arguments

• use_heuristic::Bool (default=true): whether or not InPhyNet should use a heuristic to determine whether a given merge will result in a future conflict. Setting this value to false will sharply improve runtimes but will almost always lead to algorithm failure due to merging conflicts if the input data are not very close to ground truth (even with the pairwise fallback algorithm inphynetpairwise).
• refuse_pairwise::Bool (default=false): whether InPhyNet should refuse to run the pairwise fallback algorithm inphynetpairwise if the main algorithm fails. Can lead to algorithm failure if set to true - only change if you know what you're doing.

Runs the "pairwise" version of the InPhyNet algorithm, with the following steps:

1. Instead of merging all constraints simultaneously, merge constraints[1] and constraints[2] into a new intermediate network Nhat12 (using the portions of D and namelist that pertain only to these constraints).
2. Remove constraints[1] and constraints[2] from the list of constraints.
3. Add Nhat12 to the list of constraints.
4. Repeat until constraints has only 1 network remaining: this network is the final inferred network.

This algorithm will never fail and is used as a fallback for when the main InPhyNet algorithm fails in its first round.

For details on the method's arguments, see inphynet (the arguments are identical).

internodecount(N::HybridNetwork; namelist::Union{Nothing,<:AbstractVector{String}}=nothing)

Calculates internode counts between all pairs of taxa in network N. WARNING: treats N as unrooted

internodedistance(N::HybridNetwork; namelist::Union{Nothing,<:AbstractVector{String}}=nothing)

Calculates internode distance between all pairs of taxa in network N.

Loads the distance matrix D, namelist namelist, and constraint networks constraints necessary to reproduce the merge conflict example shown in the Appendices of the InPhyNet manuscript. Further details are provided upon executing the function in the terminal.

Helper function

Gets the MRCA of nodei and nodej along their major tree.

majorinternodecount(N::HybridNetwork)

Calculates major internode counts between all pairs of taxa in the major displayed tree of network N. If N is a tree, then internode counts are as expected for a tree.

majorinternodedistance(N::HybridNetwork)

Calculates internode distances between all pairs of taxa in the major displayed tree of network N. If N is a tree, then internode distances are as expected for a tree.

Merges two unrooted SubNets into a single unrooted SubNet Returns the merged subnet AND the edges in the merged net corresponding to where reticulations will be placed if there are corresponding reticulations discovered in the constraints.

IMPORTANT: this function should NOT make copies of edges or nodes, object references are stored and used in the main merging algorithm

Updates net to include the reticulations that we've kept track of along the way in our algo but haven't placed yet.

Returns a list of networks where each entry is a copy of net pruned to include only the taxa named in each subset contained in subsets. subsets can also be an individual vector of strings instead of a nested vector (see examples below).

Example

net = readnewick("((t1,t2),(t3,t4));")
prune_network(net, [["t1", "t2"], ["t3", "t4"]])
> 2-element Vector{HybridNetwork}: (t1, t2); and (t3, t4);

prune_network(net, ["t1", "t2", "t3"])

Helper function that removes redundant edges in the graph that exist when some hybrids are pruned from the graph.

If any constraints are unrooted, picks a root node from any node directly under the root (somewhat randomly).

Performs subset decomposition as outlines in SATe-I on inittree. Returns vector of vector of names, e.g. [["a", "b"], ["c", "d", "e"]]

Splits tre into two trees at its longest branch.

Updates constraint networks after (i, j) with names (nodenamei, nodenamej) have been merged. Also updates reticmap to keep track of any reticulations that get removed in this process.

By convention we keep nodenamei and replace node names with nodenamej

Helper function for manipulating graph adjacency lists.