Claddis (version 0.7.0)

find_costmatrix_minimum_span: Finds a minimum spanning tree of a costmatrix

Description

Given a costmatrix, returns a shortest tree connecting every state.

Usage

find_costmatrix_minimum_span(costmatrix)

Value

A data.frame object describing a minimum spanning tree or minimum weight arboresence as a series of edges or arcs.

Arguments

costmatrix

An object of class costMatrix.

Author

Graeme T. Lloyd

Details

The minimum parsimony length a phylogenetic hypothesis can have depends on both the costmatrix of transition costs and the states actually sampled. If the costmatrix rows and columns 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.

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

find_shortest_costmatrix_path

Examples

# Make a four-state ordered character costmatrix:
ordered_costmatrix <- make_costmatrix(
  min_state = "0",
  max_state = "3",
  character_type = "ordered"
)

# Find length of shortest spanning tree of costmatrix:
find_costmatrix_minimum_span(costmatrix = ordered_costmatrix)

# Make a four-state unordered character costmatrix:
unordered_costmatrix <- make_costmatrix(
  min_state = "0",
  max_state = "3",
  character_type = "unordered"
)

# Find length of shortest spanning tree of costmatrix:
find_costmatrix_minimum_span(costmatrix = unordered_costmatrix)

# Make a four-state irreversible character costmatrix:
irreversible_costmatrix <- make_costmatrix(
  min_state = "0",
  max_state = "3",
  character_type = "irreversible"
)

# Find length of shortest spanning tree of costmatrix:
find_costmatrix_minimum_span(costmatrix = irreversible_costmatrix)

# Make a four-state Dollo character costmatrix:
dollo_costmatrix <- make_costmatrix(
  min_state = "0",
  max_state = "3",
  character_type = "dollo"
)

# Find length of shortest spanning tree of costmatrix:
find_costmatrix_minimum_span(costmatrix = dollo_costmatrix)