**Clade**- For an unrooted tree, a clade is a group of taxa that may be separated from the rest of the tree by breaking a single branch. For a rooted tree, a clade is all taxa in a subtree of the tree.
**Connected component**- A connected component of a graph is a maximal set of nodes of the graph and the set of edges of the graph between those nodes in which there is a path from any node in the set to any other node in the set.
**Cycle (of a a permutation)**- For an unsigned permutation,
`p`

, a cycle is a minimal sequence of integers`(a_0, a_1, ..., a_m)`

where`p(a_i) = a_(i+1)`

for`i=0,..,m-1`

and`p(a_m) = a_0`

. **Endpoint**- An endpoint of a gray edge
`(i,j)`

is either`i`

or`j`

. **GNU**- "GNU's not UNIX".
Free software (such as the C compiler
`gcc`

, and the C++ compiler`g++`

) are available at the web site`www.gnu.org`

. **Gray edge (of a permutation)**- A gray edge of an unsigned
permutation
`p`

is a pair of integers`(i,j)`

such that`i`

and`j`

differ by more than 1 and`p(i)`

and`p(j)`

differ by exactly 1. **Hurdle**- A hurdle of a unsigned
permutation (of size
`n`

) is an unoriented connected component of the overlap graph which consists of exactly one segment. Here a segment of an unoriented connected component is defined to be a maximal interval of integers (in`[0..n-1]`

) where every integer in the interval is either an endpoint of a node (which itself is a gray edge of the permutation) of the unoriented connected component, or is not an endpoint of any node of any unoriented connected component. The set`union([a..n-1],[0..b])`

is considered to be a single interval. **Internal node**- A non-leaf node of the tree. An internal node has more than one edge.
**Markov chain**- A sequence of random variables in which the distribution of each random variable depends only on the value of its predecessor.
**Markov chain Monte Carlo**- A computational technique for the numerical evaluation of high-dimensional integrals by simulating a Markov chain on a parameter space.
**Metropolis-coupled Markov chain Monte Carlo**- A variant of Markov chain Monte Carlo in which multiple chains are run in parallel, each with a different temperature. Only the information from the cold chain is recorded. Periodically, trees between chains may be swapped.
**Metropolis-Hastings**- The main form of Markov chain Monte Carlo. The algorithm provides a probabilistic rejection rule to reject some proposed moves of an arbitrary irreducible Markov chain so that the resultant Markov chain has the desired stationary distribution.
**Named clade**- A clade of particular interest. Named clades are maximal clades of at least two taxa which appear as a monophyletic group at least a specified proportion (greater than 50%) of all sampled tree topologies and having fewer than a specified number of subtree topologies.
**Unoriented edge**- A gray edge
`(i,j)`

of an unsigned permutation in which either`i`

or`j`

is odd, but not both. **Unoriented connected component (of the overlap graph)**- A connected component of the overlap graph in which all nodes (hence gray edges) are unoriented.
**Overlap graph**- For an unsigned permutation, an overlap graph is defined by taking the nodes to be the gray edges of the permutation and the edges defined as follows: There is a edge of the overlap graph from gray edge A to gray edge B if and only if edges A and B cross, i.e., the interval defined by the endpoints of A and that of B intersect and neither is a proper subset of the other.
**Phylogeny**- A tree that describes the evolutionary history of a group of species or taxa.
**Permutation**- Either a signed permutation or an unsigned permutation.
**Phylogeny**- A tree that describes the evolutionary history of a group of species or taxa.
**Prior distribution**- The probability distribution of one or more parameters before observation of data. Ideally, it represents the prior belief of the researcher. Frequently, a flat, ignorance prior may be adopted.
**Posterior distribution**- The conditional probability distribution of one or more
parameters, after observation of data. The posterior distribution is
proportional to the product of the likelihood and the prior distribution. A
**joint posterior distribution**describes the distribution of more than one random variable. **Reversal**- An operation affecting permutations. A contiguous sequence of elements is replaced by the sequence in reversed order. In a signed permutation, a reversal also changes the signs of all elements in the sequence, i.e., the elements are negated.
**Reversal list**- A list of reversals. The reversals are applied sequentially to the permutation.
**Signed permutation**- An ordering of the numbers [+/-1.. +/-n] for some n. The elements
are signed. For permutation
`p`

,`p(i)`

refers to the`i`

th element in the ordering, with`p(0)`

denoting the first element. A corresponding unsigned permutation can be obtained by replacing each positive element`x`

by`2*x-1, 2*x`

and each negative element`-x`

by`2*x-1, 2*x`

and then appending 0 to the beginning of the new list and`2*n-1`

to the end of the list. **Temperature**- A variable used in Metropolis-coupled Markov chain Monte Carlo. The temperature affects the likelihood of acceptance of a proposed tree and also affects the likelihood that two chains will accept a proposed tree swap.
**Tree topology**- The shape and leaf labeling of the tree.
**Unsigned permutation**- An ordering of the numbers [0..n-1] for some n. For permutation
`p`

,`p(i)`

refers to the`i`

th element in the ordering with`p(0)`

denoting the first element.

Back to the table of contents.

This page was most recently updated on June 29, 2004.

badger@badger.duq.edu