internal documentation

BlobFreq{N,P}

Frequency of one non-trivial blob partition, and frequency of its circular orders and taxon blocks whose parent in the blob is a hybrid node.

• The partition associated with a blob in a network is the partition into taxon blocks from the connected components of the network after the blob (nodes and edges) is removed from the network. Each part is represented by an N-tuple of booleans, where entry i says if taxon number i is in or out of this part.
• Different blobs with the same partition can have different circular orders of their taxon blocks. A blob does not necessarily admits a circular order.
• For each part in the partition, this part is a "hybrid" for this blob if it is adjacent to the blob at a hybrid node.

P is the number of parts (taxon blocks) in the partition; 3 or more. N is the number of leaves (taxa) in the network. 3 or more.

SplitFreq{N}

Frequency of one non-trivial taxon block, typically considered as describing an unrooted bipartition (or split) of the N taxa into P=2 parts.

It is non-trivial if each part has at least 2 taxa, that is: the block is not empty, not full, does not contain a single taxon, or all but a single taxon.

The taxon block is represented by an N-tuple of booleans, where entry i says whether taxon number i is in or out of this block. The canonical taxon block used to describe an unrooted bipartition is the block that does not contain the last taxon, such that its last entry N is false.

_bipartition_edgeindices(refbps, hwmatrix, edgenum2idx)

For each non-redundant bipartition in refbps, find the corresponding edge index and edge number by matching the split against the hwmatrix.

_blobnode_blobedges

Output: (blobnode, blobedge_numbers) where

• blobnode is the vector of entry nodes, one per blob and
• blobedge_numbers has one vector per blob, each being a vector with one edge number per taxon block.

Warning: uses net.partition and internal fields .inte1 and .intn1. These fields should store the edge's bicomponent number, and the node's blob number (if non-trivial, 0 if the node is a trivial blob). They do if net was already traversed by count_blobpartitions, which calls process_biconnectedcomponents! to build net.partition. The blob number should also be its index in the input refblobs.

assumptions about input arguments, met after calling count_blobpartitions with the same minBdegree:

• blobdegree: vector of length net.partition, with 1 degree per bicomponent: blob degree if the bicomponent is at the top (entry) of a blob, 0 if it is trivial (1 edge) or below another bicomponent in the same blob.
• blobnode has 1 node for each blob of degree ≥ minBdegree, in the same order as they appear in blobdegree (as in a net.partition)

add_blobnode!(tree, ni, ei, blobpartition, weight)

Add nodes (numbered ni etc.) and edges (numbered ei etc.) in tree to add blobpartition, assumed compatible with edges already in tree. The node index ni is decremented, and the edge index ei is incremented.

Output: (n, ei) where

• n is the newly created node in tree whose removal disconnects the taxon set into the input blob partition, and
• ei is a vector of edge indices in tree.edge: tree.edge[e[j]] is the edge whose removal disconnects taxon block j of blobpartition from its complement.

If the blob has P ≥ 3 taxon blocks, these blocks are assumed to form a partition of the full taxon set. If it is blob-compatible with all blobs already in tree, then k nodes and k edges are added, where k is the number of non-trivial taxon blocks. If the blob is tree-compatible but not blob-compatible with the tree, then fewer nodes and edges are added with a warning, or an error is thrown.

The blob's weight is stored in the corresponding node's .fvalue.

As blob partitions are agnostic about the root, the output tree should be considered unrooted. The added edges correspond to using the last taxon as outgroup: an edge's cluster of descendants does not contain the last taxon.

Assumptions (none are checked): tree is a tree, P ≥ 3, taxon blocks are non-empty and do form a partition, assumptions in add_clusteredge!, and taxon j is the node number j in tree incident to tree.edge[j], as built from startree.

add_canonical_circularorder!(circularorder_dictionary, indexmap, netweight)

1. Find the clockwise (and counter-clockwise if necessary) circular permutation(s) of indexmap, starting at the index for value 1. For example, for vector [5, 1, 3, 2, 4], these are: 1,3,2,4,5 and 1,5,4,2,3. These are the 2 canonical ways of coding their shared circular order: starting from value 1 and circling in one or the other direction.
2. Add this circular order to the input dictionary: if already present (in clockwise or counterwise direction) then its frequency is increased by netweight. Otherwise, a new entry with frequency netweight is added to the dictionary.

add_clusteredge!(tree, ni, ei, cluster, weight, supportaslength;
    nowarning=false)

Add a node (numbered ni) and its parent edge (numbered ei) in tree, whose set of descendants is cluster, described by a 0/1 vector. The node index ni is decremented, and the edge ei is incremented.

Output: newly created edge if successful (whose child node is the newly created node), otherwise nothing with a warning unless nowarning=true.

The edge & node addition is unsuccessul if the cluster is empty, or is the full taxon set, or if it is already present in tree. Adding it a second time would result in a new node of degree 2, which is avoided.

Assumptions:

• tree is a tree (not checked)
• cluster is compatible with tree (considered rooted)
• leaf j, whose cluster membership is cluster[j], is the node number j in the tree, that is, is it node n = tree.node[i] such that n.number is j.

Algorithm: the tree is traversed before being modified, to find:

• Q1: which node lca should be the parent of the new node, and
• Q2: which children of lca should become children of the new node.

To do so: .booln2 and .booln3 are used to store, for each node

• .booln2: Does 1+ descendant(s) of node ∈ clade ?
• .booln3: Is {node's descendants} ⊆ clade ?

Then, the answer to Q1 is the lowest node such that .booln2 && !.booln3, and the answer to Q2 is all lca's children with .booln2 && .booln3.

add_clusteredge_weight!

Find or create an edge e whose descendant taxa is the input cluster, and stores the input weight in the edge's field .y, and as its length with option supportaslength=true. Output: edge e.

The input cluster may already exists in the input tree. Unlike add_clusteredge!, no warning is thrown. The appropriate edge is found, its fields (.y and perhaps length) are modified to store the weight, and this edge is returned.

biedges should give the index of edges in netedge. optional: bpe_nums for the bipartition edge numbers. Otherwise edge numbers are assumed to be equal to edge indices.

blobcompatible(A, B)

true if two partitions A and B of N taxa are blob-compatible; false otherwise.

A and B are compatible if there exists i and j such that all parts of B except Bⱼ are subsets of Aᵢ. Then, since A and B are partitions of the same set (not checked!), all parts of A except Aᵢ are subsets of Bⱼ. This reduces to tree-compatibility when both A and B are bipartitions.

If A or B is given as a single cluster, it is considered as unrooted, as one part of the bipartition (A,Aᶜ) or (B, Bᶜ) where Aᶜ denotes the complement of A.

blobtaxonsetpartition!(visitedbcc, blobdegree, net, bicomponent, bidx,
    edgemap, hardwiredclustermatrix, taxon2index, ntaxa)

Depth-first traversal of a blob B starting from its top bicomponent, to collect its taxon blocks, which form a partition of the full set of N taxa. Each taxon block (or split) corresponds to a cut-edge uv adjacent to the blob, with u ∈ B in the blob and v ∉ B. The taxon block for uv is reprented by an N-tuple of 0/1 values with 1 at index i = taxaindex[label] if the taxon named label is a descendant of uv, and 0 otherwise. If u ∈ B is a hybrid node incident to some exit edge uv, then the taxon block associated with this edge is considered "hybrid" for this blob.

Output: (splits, hybrids, islevel1) where

• splits is the blob's partition as a tuple of N-tuples, listed in a "half" circular order if the blob is level-1: from highest to lowest along one side then along the other side.
• hybrids is the vector of indices in splits, of taxon blocks that are hybrid for the blob.
• islevel1 is true all bicomponent in the blob have a reticulation number ≤ 1; false otherwise. For binary networks, a non-trivial blob has a single biconnected component, and its level is its number of hybrid nodes.

Also:

• visitedbcc may be modified. If several biconnected components are part of the same blob starting at bicomponent indexed bidx (in net.partition), then the indices of these other bicomponents are added to visitedbcc.
• blobdegree is incremented by the number of taxon blocks found.

Warning: used internal fields

• .inte1 set by process_biconnectedcomponents! is used (not modified)
• .intn1 is modified to track to store the node's blob, if non-trivial (a blob may contain more than 1 bicomponent). This field should be initialized earlier (to a value ≤ 0).
• .boole1 is modified to track if a hybrid edge may be traversed, still; should be initialized earlier (to true).

blobtaxonsetpartition!(splits, hybrids, visitedbcc, blobdegree, islevel1,
    entrynode, bidx, edgemap, hardwiredclustermatrix, taxon2index, net)

Helper to accumulate entries in splits and hybrids. Internal fields:

• .inte1 used but not modified: should store the index of an edge's biconnected component.
• .intn1 updated to store the blob index that a visited node is in: index of the first biconnected component in this blob.
• .boole1 set to false for all partners of an edge that will be traverered.

In splits, only the children taxon blocks are gathered, from exit cut-edges, but recursively across all bicomponents in the blob (which may occur in non-binary networks).

check_nonnumericnames(taxa)

Check that the vector of taxa contains names that do not start with "" followed by a positive integer, such as "12". The exception is that the ith taxon taxa[i] is allowed to be "_i".

Output: nothing if the conditions are met, otherwise the first index i such that taxa[i] is _n with n ≠ i.

cluster_fromHmatrix(M, i, N)

Tuple of booleans from row i of the hardwired-cluster matrix M on N taxa, considering the phylogeny as rooted: 0/1 values as they are, not switched.

See split_fromHmatrix for the unrooted version.

consensus_bipartitions!(splitcounts::Vector{SplitFreq{N}},
    proportion::Number, numtrees::Number)

Filter splitcounts to keep only the bipartitions whose frequencies are greater than proportion × numtrees, or equal to numtrees when proportion is 1. Bipartitions with frequency weight over 50% must be compatible with each other. Bipartitions are retained one by one, from most to least frequent, so long as they are compatible with bipartititions previously kept.

The result can be passed to tree_from_bipartitions to construct the associated consensus tree topology. proportion = 1 corresponds to the strict consensus tree, proportion = 0.5 corresponds to the majority-rule consensus tree and proportion = 0 to a greedy consensus tree.

Output: splitcounts modified, with some entries filtered out, and sorted by frequency (from least to most frequent) if proportion<0.5.

Assumption: all counts are positive.

Note that we use the term "bipartitions" here, which means splits of the taxon set when ignoring the root. But this function can equally be used for clusters (or clades) obtained as an edge's descendants when knowing the root position.

Example

julia> const PS = PhyloSummaries; # to use internals with less typing

julia> bp = [(true,false), (false,false), (true,true)]; freq=Ref.([3.,1,4]);

julia> splitcounts = [PS.SplitFreq(x,y) for (x,y) in zip(bp, freq)]
3-element Vector{PhyloSummaries.SplitFreq{2}}:
 SplitFreq on 2 taxa, taxa in split cluster: 1, frequency: 3
 SplitFreq on 2 taxa, taxa in split cluster: , frequency: 1
 SplitFreq on 2 taxa, taxa in split cluster: 1,2, frequency: 4

julia> PS.consensus_bipartitions!(splitcounts, 0.5, 4)
2-element Vector{PhyloSummaries.SplitFreq{2}}:
 SplitFreq on 2 taxa, taxa in split cluster: 1, frequency: 3
 SplitFreq on 2 taxa, taxa in split cluster: 1,2, frequency: 4

julia> splitcounts = [PS.SplitFreq(x,y) for (x,y) in zip(bp, freq)]; # reset

julia> PS.consensus_bipartitions!(splitcounts, 0, 4) # sorted
3-element Vector{PhyloSummaries.SplitFreq{2}}:
 SplitFreq on 2 taxa, taxa in split cluster: , frequency: 1
 SplitFreq on 2 taxa, taxa in split cluster: 1, frequency: 3
 SplitFreq on 2 taxa, taxa in split cluster: 1,2, frequency: 4

count_bipartitions!(counts, net, taxa, rooted)

Count bipartitions in net, and add them to counts. If a new bipartition is found, a new key is added to counts with value 1. If net has a bipartition already present as a key in counts, then the corresponding value is incremented by 1. net is not modified.

By default, input trees are considered unrooted, and bipartitions are considered. Use rooted=true to consider all input trees as rooted, in which case clades (rather than bipartitions) are used to build the output rooted consensus tree.

Only non-trivial (not all 0s or all 1s) splits contribute to the count totals.

If the tip labels in net do not match those in taxa (as a set), then an error will be thrown indirectly (via PhyloNetworks.hardwiredclusters).

count_blobpartitions(networks, taxa, minimumblobdegree,
    require_level1=false, netweights=nothing)

(blob_vec, bipart_vec) where blob_vec is a vector of BlobFreq{ntax} object (ntax being the number of taxa), bipart_vec is a vector of SplitFreq{ntax} objects. All input networks must have the same set of taxa. If require_level1 is true, an error is thrown the first network with a blob whose level is not ≤ 1.

In blob_vec, each entry is for a non-trivial blob multi-partition: a partition of all taxa into ≥ 3 taxon blocks. Each part, or taxon block, in each partition, is represented by a 0/1 tuple with 1 at index i to indicate if taxa[i] is part of the block (0 if not). In bipart_vec, each entry is a bipartition (2 taxon blocs), counted if it was not redundant with a non-trivial blob multi-partition.

Each object also has information about the frequency of the blob multi-partition or non-redundant bipartition in networks. Each blob object also stores the frequency of each circular order for that partition, and the frequency with which each taxon blob is hybrid for the blob.

A blob is a 2-edge connected component. In a non-binary network, a blob may be the union of several biconnected components.

A non-redundant bipartition comes from a cut-edge in an input network N. A cut edge contributes and entry and is counted in a bipart_vec if it is not redundant with a non-trivial blob of N, that is, if one of its two taxon blocks is not also a taxon block of a non-trivial blob in N.

Side effects and internal fields:

• .inte1 set by process_biconnectedcomponents! is used (and not modified)
• .intn1 stores 0 if a node is a singleton blob, and the node's blob index otherwise: index of the first bicomponent in the blob (which are pre-ordered).
• .boole1 of edges, to visit hybrid nodes once and in "half" circular order.

See also: consensus_treeofblobs

count_blobpartitions!(blobs, biparts, net, taxa, minBdegree,
    require_level1, netweight)

Helper for count_blobpartitions. Update the entries in the vector of blobs and in the vector of biparts corresponding to the multi-partitions defined by all "interesting" blobs and non-redundant bipartitions defined by cut-edges non-adjacent to some interesting blob, in one network net. If a new blob partition or non-redundant bipartition if found, that was absent from blobs or biparts respectively, a new entry is created in the vector.

Output: (hwmatrix, edgemap, blobdegree)

• hwmatrix: matrix describing net's hardwired clusters (1 per internal edge)
• edgemap: dictionary mapping each edge number to its row in hwmatrix
• blobdegree: vector of length net.partition (# of biconnected components) with 1 degree per bicomponent: blob degree if the bicomponent is at the top of (entry to) a blob, or 0 if the bicomponent is trivial (1 edge) or below another bicomponent in the same blob.

Notes:

• A "blob" here means a non-trivial blob with at least 1 hybrid node.
• A blob may be the union of 1 or more biconnected components (blobs partition nodes, bicomponents partition edges).
• A blob is "interesting" if its degree (number of adjacent cut edges) is at least minBdegree.
• Trivial biconnected components correspond to cut edges (and are not included in any blob, unlike non-trivial bicomponents). They are counted when they are not redundant with (not incident to) some "interesting" blob.
• A chain of 2-blob leads to multiple cut-edge sharing the same bipartition. This bipartition is counted only one (or not counted if it is trivial or adjacent to an interesting blob); as if 2-blobs had been suppressed.

count_blobpartitions!(blobs, visitedbcc, net, taxaindex, minBdegree,
    blob, bidx, hwmatrix, edgemap, require_level1, netweight)

Update the vector of blobs frequencies, and visitedbcc (to track biconnected components already visited) for a single potentially interesting non-trivial blob, starting from the bidx-th biconnected component in net.

Output: degree of the blob starting at the bidx-th biconnected component, that is, number of cut-edges adjacent to that blob.

count_nonredundantbipartitions!(bipart_vec, blobdegree, net, ...)

Gather non-redundant cut-edges from net and add them to bipart_vec (or increment their frequency). The field .intn1 is used to know which blobs are adjacent to a cut edge, and blobdegree to know if either of these blobs is "interesting"

expand_blobcycles!(net, blobnode_vector, edgeblockindices_vector,
    blobpartition_vector, nnets, outgroup=nothing)

Modify each blob node in net into a cycle. If specified, net is rooted at the outgroup taxon. Blobs are expanded sequentially, from most frequent to least frequent. Each blob node is expanded using a circular order of highest frequency. The hybrid node in the cycle is one of highest frequency among those compatible with previous expanded blobs, or some child of the blob node otherwise.

Weights (frequency / nnets) of blobs, circular order and hybrid clades are stored in specific nodes' .fvalue:

• The blob weight should be stored in the fvalue of the blob node if the input net is originally from tree_from_blobpartitions. The original blob node will become the entry (or root) of the blob cycle.
• The weight of the circular order is stored in the fvalue of all non-entry tree nodes in the cycle.
• The weight of a hybrid clade is stored the hybrid node's fvalue.

In each cycle, the edges' .inte1 and the nodes' intn1 are set to a blob identifier (its index in the input vectors).

filter_sort_compatible_partitions!(blobpartitions, bipartitions, nnets, proportion)

Filter out blob- and bi-partitions with frequency ≤ proportion; sort each vector of blobpartitions and bipartitions by frequency (from smallest to largest); filter out any partition not compatible with another of higher frequency (giving preference to a blob over a bipartition if tied).

Blob-compatibility is used, which reduces to tree-compatibility when both partitions are bipartitions.

Bipartitions redundant with a retained blob are not filtered out.

findmatchingblob(blobs::Vector{BlobFreq{N}}, splits) where N

Index in blobs and permutation to match the blob partition of splits. Output:

• (i,idxmap) if blobs[i] matches splits using permutation vector idxmap, that is: splits[k] is blobs[i].partition[idxmap[k]] for all k.
• (nothing, nothing) if no match is found.

Assumption: the splits partition the full set of N taxa, and so do the taxon blocks of each blob. In particular, splits are distinct from one another, and taxon blocks from a given partition are also distinct.

blobedges should give the index of edges in netedge. optional: blobedges_nums for edge numbers. Otherwise edge numbers are assumed to be equal to edge indices.

isnotdisjointsplit(a, b)

true if a ∩ b is non-empty (a and b share 1 or more taxa), false otherwise. a and b are splits (or clusters) on N taxa, encoded as tuples of N booleans.

isredundantsplit(v, b)

true/false if v does / does not represent one taxon block of blob (or multi-partition) b, with v considered as unrooted.

issubsetsplit(a, b)

true if a ⊆ b (all taxa in a are also in b), false otherwise. a and b are splits (or clusters) on N taxa, encoded as tuples of N booleans, with a[i] true to mean that taxon i ∈ a.

istrivialsplit(v)

true/false if v does / does not represent a trivial split. v should contain booleans or 0/1 values. A split is trivial if it has: all 0s, or all 1s, or a single 0, or a single 1.

optimalhybridblocks(blobparts)

Find the hybrid block placement that maximizes the total hybrid frequency summed across all blobs, under the constraint that hybrid blocks are compatible with each other.

Output: vector best_hybridblock listing the best choice of hybrid block index for each blob.

3 subscores are considered, according to 3 types of blobs: of degree ≥5, 4 or 3. The total score is the sum of hybrid frequency over all blobs. The second subscore is the sum of hybrid frequencies over blobs of degree ≥4 (excluding blobs of degree 3, in which the hybrid clade might be non-identifiable and of uncertain placement), and the third subscore is over blobs of degree ≥5 (excluding blobs of degrees 3 or 4). In case of tied total scores, the ties are broken to maximize the second subscore, or the third subscore in case of ties again.

The optimal choice of hybrid block combination is done by considering each leaf x as a potential outgroup, then finding the best. Other root placements need not be evaluated assuming that the network is level-1 and all blobs have 3 or more taxon blocks. A hybrid block is compatible with x being an outgroup if it does not contain x, such that, for each blob partition, we only need to consider the 2 hybrid blocks of highest and second-highest frequencies. (In case of ties, including among block of 0 hybrid frequencies, the 'first' tied block is chosen – first as listed in the circular order.)

split_fromHmatrix(M, i, N)

Tuple of booleans from row i of the hardwired-cluster matrix M on N taxa, considering the phylogeny as unrooted: 0/1 values are switched if necessary, to make sure that the last entry is false.

See cluster_fromHmatrix for the rooted version.

startree(taxa)

Star tree t such that t.node lists all leaves named after the N taxa in that order: for i in 1 through N: node n = t.node[i] has n.number = i and n.name = taxa[i]. It is incident to edge e = t.edge[i] which has e.number = i. The root node is last, t.node[N+1], has number N+1 and name "_N+1".

tree_from_bipartitions(taxa::Vector{String},
    clustercounts::Vector{SplitFreq{N}},
    ntrees::Number,
    supportaslength::Bool)

Construct a tree on N taxa from a compatible set of clusters, as a PhyloNetworks.HybridNetwork object. Each cluster is represented as a tuple key b, and is given a weight: its value clusters[b] divided by ntrees. For each cluster, a node n and its parent edge e are added to the tree, whose descendant taxa is the set taxa[i] for indices i such that b[i] is true.

The cluster's weight is stored in e.y. With option supportaslength=true, the cluster weight is also in e.length.

Assumptions:

• taxa is of length N: same size as each cluster
• the input clusters are pairwise tree-compatible, which is the condition for them to be the clusters of a valid rooted tree.

Used by: consensustree

tree_from_blobpartitions

Tree summarizing the input partitions: with a node for each input blob and an edge (if not redundant) for each input bipartition. This tree should be considered unrooted, in part because blob partitions do not have root information (all their taxon blocks are listed).

Output: (tree, blobnode_vec, blockedgeindices_vec, bipartedgeindices_vec) where the last 3 components list the nodes (in the tree) corresponding to each input blob, the edges corresponding to each taxon block in each input blob, and the edges corresponding to each non-redundant bipartition.

A blob's weight is stored in the corresponding node's .fvalue. A bipartition's weight is stored in the corresponding edge's field .y. With option supportaslength=true, this weight is also stored in the bipartition edge's .length.

Assumptions (not checked):

1. each bipartition is represented by the taxon block that does not contain the last taxon
2. bipartititions are not trivial: they separate at least 2 taxa from at 2 other
3. blobs are correct partitions, with P ≥ 3 parts at least
4. blob partitions and bipartitions are all compatible with each other: any 2 blobs from blobpartitions are blob-compatible; any 2 splits from bipartitions are tree-compatible; and any blob and split are blob-compatible.

Calls add_blobnode! and add_clusteredge!, which use internal fields .booln2 and .booln3.

treecompatible(a::NTuple{N,Bool}, b::NTuple{N,Bool})

true / false if two clusters a and b are / are not tree-compatible.

If A is the cluster of descendants of a (with true entries in a) and if B is the cluster of descendant of b, these 2 clusters are tree-compatible if there exists some tree that has both clusters. This can be checked by the condition: A∩B is empty, or A⊆B, or B⊆A.

update_bipartitionfrequency!(refbps, samplebps)

Update the frequency of each bipartition in refbps to match that from samplebps. A bipartition not found in samplebps is not modified – which assumes that its frequencies had been initialized to 0.

Bipartitions are considered unrooted: so a bipartition in samplebps is a match if either its clade or its complement matches that from refbps.

update_blobcircorderfrequency!(refblobs, sampleblobs)

Update the frequency and circular order dictionary of each "reference" blob partition blob (item in refblobs), to match that from sampleblobs. A reference blob partition not found in sampleblobs is not modified – which assumes that its frequencies had been initialized to 0.

Note the blobs hybrid dictionaries are not updated. For this, see instead update_hybridclusterfrequency! to use the frequencies of hybrid clades aggregated over all sample blobs (a hybrid clade can originate below different blobs, of different partitions).

update_hybridclusterfrequency!(blobfreq_vector, clusterfreq_dict)

In each BlobFreq item blob in blobfreq_vector, replace hybrid frequencies in blob.hybrid by those in clusterfreq_dict. Note that the list of hybrid clusters in blob may be expanded with clusters not yet listed but present in clusterfreq_dict, for any cluster compatible with the blob partition. Also, clusters are rooted here (hybrid descendants). Assumption: any part of a blob is a cluster (key) in clusterfreq_dict.