BADGER

Bayesian Analysis to Describe Genomic Evolution by Rearrangement

Version 1.02 beta, June 11, 2004

Glossary

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 ith 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 ith element in the ordering with p(0) denoting the first element.

Back to the table of contents.