BADGER
Bayesian Analysis to Describe Genomic Evolution by Rearrangement
Version 1.02 beta, June 11, 2004
Copyright © 2004 by Bret Larget & Don Simon
Please note that the definitions for some terms may be specific to BADGER.
- 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