pegas (version 1.4)

mst: Minimum Spanning Tree and Network

Description

Computes a minimum spanning tree (MST) using Kruskal's algorithm, the minimum spanning network using Bandelt et al.'s algorithm, or the randomized minimum spanning tree (Paradis 2018).

Usage

mst(d)
msn(d)
rmst(d, B = NULL, stop.criterion = NULL, iter.lim = 1000,
     quiet = FALSE, random = FALSE)

Value

an object of class "haploNet".

Arguments

d

a distance matrix, either as an object of class "dist", or a (square symmetric) matrix.

B

number of randomizations (ignored if random = FALSE).

stop.criterion

the stopping criterion if B is not given (see details; ignored if random = FALSE).

iter.lim

the maximum number of iterations (ignored if random = FALSE).

quiet

a logical value specifying whether to indicate progress of calculations.

random

the default is to find all MSTs compatible with the data. If TRUE, the random algorithm described in Paradis (2018) is used.

Author

Emmanuel Paradis

Details

The new default implementation of rmst uses an algorithm which finds all possible MSTs compatible with the data. This gives the same results than random = TRUE if the number of iterations is sufficienly large.

If random = TRUE, the calculations stop when no new links are found after a number of successive iterations specified by stop.criterion. By default, this number is ceiling(sqrt(n)) where n is the number of observations. This criterion is ignored if B is given, or if n < 6 in which case complete enumeration is done. In all cases, no more than iter.lim iterations are done.

The method implemented in rmst is not directly related to the algorithm of the same name summarized by Ramachandran (2008).

References

Bandelt, H. J., Forster, P. and Rohl, A. (1999) Median-joining networks for inferring intraspecific phylogenies. Molecular Biology and Evolution, 16, 37--48.

Kruskal, J. B., Jr. (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7, 48--50.

Paradis, E. (2018) Analysis of haplotype networks: the randomized minimum spanning tree method. Methods in Ecology and Evolution, 9, 1308--1317.

Paradis, E. (2025) An efficient algorithm to find all minimum spanning trees. Journal of Complex Networks, 13, cnaf004.

Ramachandran, V. (2008) Randomized Minimum Spanning Tree. In: Kao, M. Y. (ed) Encyclopedia of Algorithms. Pages 1747--1750. Springer, Boston, MA.

See Also

haploNet, mjn

Examples

data(woodmouse)
d <- dist.dna(woodmouse, "n")
(r <- mst(d))
plot(r)

## a case where the RMST and the MJN are identical:
x <- c(">A", "TAAGTGCAT", ">B", "TAAATGCAT", ">C", "TAGGTGCAT", ">D", "TAAGTACAT",
       ">E", "TAAGTGTAT", ">F", "TAAGTACAC", ">G", "TAAGTACGT", ">H", "CAAGTACAC",
       ">I", "CAAGCACAC", ">J", "CAAGTACAT", ">K", "CGAGTACAT", ">L", "TAAGTACGC",
       ">M", "CAAGCACAT")
fl <- tempfile()
cat(x, file = fl, sep = "\n")
x <- read.dna(fl, "f")
tr <- rmst(dist.dna(x, "n"))
ts <- mjn(x)
stopifnot(all.equal(tr, ts))
unlink(fl)