guessMSTRoots: Guess the roots of a MST

In LTLA/TrajectoryUtils: Single-Cell Trajectory Analysis Utilities

Guess the roots of a MST

Description

Pick nodes to use as the root(s) of an MST using a variety of ad hoc methods.

Usage

guessMSTRoots(
  g,
  method = c("degree1", "maxstep", "maxlen", "minstep", "minlen")
)

Arguments

g	A graph object containing a MST. All nodes should be named.
method	String specifying the method to use to pick the root.

Details

When method="degree1", an arbitrary node of degree 1 is chosen as the root for each component. This aims to reduce the number of branch events by starting from an already-terminal node.

When method="maxstep", we pick the node of degree 1 that has the highest average number of steps to reach all other nodes of degree 1. This aims to maximize the number of shared clusters between different paths when traversing g from the root to the other terminal nodes, under the philosophy that branch events should occur as late as possible. When method="maxlen", we instead pick the node of degree 1 that has the highest average distance to reach all other nodes of degree 1. This also considers the distance spanned by each cluster.

When method="minstep", we pick the node that has the lowest average number of steps to reach all nodes of degree 1. This aims to minimize the number of shared clusters between different paths under the philosophy that branch events should occur as early as possible. When method="minlen", we instead pick the node that has the highest average distance to reach all nodes of degree 1.

Value

A character vector containing the identity of the root for each component in g.

Author(s)

Aaron Lun, based on code by Kelly Street

Examples

library(igraph)
edges <- c("A", "B", "B", "C", "C", "D", "C", "E")
g <- make_graph(edges, directed=FALSE)

guessMSTRoots(g)
guessMSTRoots(g, method="maxstep")
guessMSTRoots(g, method="minstep")

# Works with multiple components.
edges2 <- c(edges, "F", "G", "G", "H")
g2 <- make_graph(edges2, directed=FALSE)
guessMSTRoots(g2)

LTLA/TrajectoryUtils documentation built on Feb. 5, 2024, 11:56 a.m.