find_stategraph_minimum_span {Claddis} | R Documentation |
Finds a minimum spanning tree of a stategraph
Description
Given a stategraph, returns a shortest tree connecting every state.
Usage
find_stategraph_minimum_span(stategraph)
Arguments
stategraph |
An object of class |
Details
The minimum parsimony length a phylogenetic hypothesis can have depends on both the stategraph of transition costs and the states actually sampled. If the stategraph vertices already represent sampled states (the assumption here) then this minimum length is reduced to a graph theory problem - the minimum spanning tree or, if a directed graph, the minimum weight spanning arboresence. (NB: if there are unsampled states then the find_steiner_tree_of_stategraph
function should be used instead.) This function returns one such shortest tree (although others may exist). The sum of the weights of the edges or arcs returned is the minimum cost.
As the algorithms used are graph theory based the function operates by simply calling convert_costmatrix_to_stategraph and find_stategraph_minimum_span. In practice, if the costmatrix represents a graph (transition costs are all symmetric) then Kruskal's algorithm is applied (Kruskal 1956). If costs are asymmetric, however, then the graph representation is a directed graph (or digraph) and so a version of Edmonds' algorithm is applied (Edmonds 1967).
Note that Dollo characters represent a special case solution as although a penalty weight is applied to the edges intended to only ever be traversed once this weight should not be used when calculating tree lengths. The function catches this and returns the edges with the weight that would actually be counted for a minimum weight spanning tree.
Value
A data.frame
object describing a minimum spanning tree or minimum weight arboresence as a series of edges or arcs.
Author(s)
Graeme T. Lloyd graemetlloyd@gmail.com
References
Edmonds, J., 1967. Optimum branchings. Journal of Research of the National Bureau of Standards Section B, 71B, 233-240.
Kruskal, J. B., 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7, 48-50.
See Also
Examples
# Make a four-state ordered character stategraph:
ordered_costmatrix <- make_costmatrix(
min_state = "0",
max_state = "3",
character_type = "ordered"
)
ordered_stategraph <- convert_costmatrix_to_stategraph(costmatrix = ordered_costmatrix)
# Find length of shortest spanning tree of stategraph:
find_stategraph_minimum_span(stategraph = ordered_stategraph)
# Make a four-state unordered character stategraph:
unordered_costmatrix <- make_costmatrix(
min_state = "0",
max_state = "3",
character_type = "unordered"
)
unordered_stategraph <- convert_costmatrix_to_stategraph(costmatrix = unordered_costmatrix)
# Find length of shortest spanning tree of stategraph:
find_stategraph_minimum_span(stategraph = unordered_stategraph)
# Make a four-state irreversible character stategraph:
irreversible_costmatrix <- make_costmatrix(
min_state = "0",
max_state = "3",
character_type = "irreversible"
)
irreversible_stategraph <- convert_costmatrix_to_stategraph(costmatrix = irreversible_costmatrix)
# Find length of shortest spanning tree of stategraph:
find_stategraph_minimum_span(stategraph = irreversible_stategraph)
# Make a four-state Dollo character stategraph:
dollo_costmatrix <- make_costmatrix(
min_state = "0",
max_state = "3",
character_type = "dollo"
)
dollo_stategraph <- convert_costmatrix_to_stategraph(costmatrix = dollo_costmatrix)
# Find length of shortest spanning tree of stategraph:
find_stategraph_minimum_span(stategraph = dollo_stategraph)