Skip to contents

Nearest neighbour interchange (NNI)

Source: R/NNI.R
NNI.Rd

NNI()performs a single iteration of the nearest-neighbour interchange algorithm; RootedNNI() retains the position of the root. These functions are based on equivalents in the phangorn package. cNNI() is an equivalent function coded in C, that runs much faster.

Usage

NNI(tree, edgeToBreak = NULL)

cNNI(tree, edgeToBreak = NULL, whichSwitch = NULL)

NNISwap(parent, child, nTips = (length(parent)/2L) + 1L, edgeToBreak = NULL)

RootedNNI(tree, edgeToBreak = NULL)

RootedNNISwap(
  parent,
  child,
  nTips = (length(parent)/2L) + 1L,
  edgeToBreak = NULL
)

Arguments

tree

A tree of class phylo.

edgeToBreak

In (Rooted)NNI(), an optional integer specifying the index of an edge to bisect/prune, generated randomly if not specified. If -1, a complete list of all trees one step from the input tree will be returned. In cNNI(), an integer from zero to nEdge(tree) - nTip(tree) - 2, specifying which internal edge to break.

whichSwitch

Integer from zero to one, specifying which way to re-build the broken internal edge.

parent

Integer vector corresponding to the first column of the edge matrix of a tree of class phylo, i.e. tree$edge[, 1].

child

Integer vector corresponding to the second column of the edge matrix of a tree of class phylo, i.e. tree$edge[, 2].

nTips

(optional) Number of tips.

Value

Returns a tree with class phylo (if returnAll = FALSE) or a set of trees, with class multiPhylo (if returnAll = TRUE).

cNNI() returns a tree of class phylo, rooted on the same leaf, on which the specified rearrangement has been conducted.

NNISwap() returns a list containing two elements, corresponding in turn to the rearranged parent and child parameters.

a list containing two elements, corresponding in turn to the rearranged parent and child parameters

Details

Branch lengths are not supported.

All nodes in a tree must be bifurcating; ape::collapse.singles() and ape::multi2di() may help.

Functions

  • NNISwap(): faster version that takes and returns parent and child parameters

  • RootedNNI(): Perform NNI rearrangement, retaining position of root

  • RootedNNISwap(): faster version that takes and returns parent and child parameters

References

The algorithm is summarized in Felsenstein2004TreeSearch

See also

Other tree rearrangement functions: SPR(), TBR()

Author

Martin R. Smith (martin.smith@durham.ac.uk)

Examples

tree <- TreeTools::BalancedTree(8)
# A random rearrangement
NNI(tree)
#> 
#> Phylogenetic tree with 8 tips and 7 internal nodes.
#> 
#> Tip labels:
#>   t1, t2, t3, t4, t5, t6, ...
#> 
#> Rooted; no branch lengths.
cNNI(tree)
#> 
#> Phylogenetic tree with 8 tips and 7 internal nodes.
#> 
#> Tip labels:
#>   t1, t2, t3, t4, t5, t6, ...
#> 
#> Rooted; no branch lengths.

# All trees one NNI rearrangement away
NNI(tree, edgeToBreak = -1)
#> 12 phylogenetic trees

# Manual random sampling
cNNI(tree, sample.int(14 - 8 - 1, 1), sample.int(2, 1))
#> 
#> Phylogenetic tree with 8 tips and 7 internal nodes.
#> 
#> Tip labels:
#>   t1, t2, t3, t4, t5, t6, ...
#> 
#> Rooted; no branch lengths.

# A specified rearrangement
cNNI(tree, 0, 0)
#> 
#> Phylogenetic tree with 8 tips and 7 internal nodes.
#> 
#> Tip labels:
#>   t1, t2, t3, t4, t5, t6, ...
#> 
#> Rooted; no branch lengths.

# If a tree may not be binary, collapse nodes with
tree <- TreeTools::MakeTreeBinary(tree)

# If a tree may be improperly rooted, use
tree <- TreeTools::RootTree(tree, 1)

# If a tree may exhibit unusual node ordering, this can be addressed with
tree <- TreeTools::Preorder(tree)