The proposed phylogeny is represented by an unrooted tree. The leaves contain signed permutations representing the genome arrangements of the taxa in the data set. Internal nodes contain signed permutations representing proposed intermediate taxa. Each edge is annotated with a list of reversals that will transform the permutation in one endpoint to the permutation in the other endpoint.

At present, there are eight tree proposal algorithms in BADGER, listed below. In interpreting the illustrations, please note the following:

is a node whose permutation may be changed by the update,

, are reversals,

, are new reversals, and

is a path, rather than a direct edge.

In the diagrams, a new reversal list may differ in length from the original list. Also, nodes shown with a single adjacent edge may be leaves, or may be internal nodes whose other edges are not shown.

**Update 1**- Choose an internal node. Slide a random number of reversals from
one edge adjoining the node to another edge, changing the permutation
of the node. Create a new reversal list for the third edge from the
node.
**Update 1x**- Similar to Update 1, but instead of replacing the entire reversal
list on the third edge, replace only an initial segment whose endpoint is
randomly chosen.
**Update 2**- Choose an edge. Replace the reversal list along that edge.
**Update 2x**- Similar to Update 2 and to the update method used by York,
Durrett, and Nielsen. Choose two random points in the reversal list of
an edge and replace the reversals between those two points.
**Update 3**- Chose an internal edge. Chose another edge from each endpoint of
the chosen edge and swap the two edges, replacing their reversals
lists with new ones.
**Update 4**- Tree bisection and reconnection: Chose an internal edge and delete
it along with its endpoints. Choose edges from each of the resulting
two connected components, select a point in the reversal lists of
each, and connect those points together by a new edge, randomly
choosing its new reversal list.
**Update 5**- Choose an internal edge. Slide one endpoint of the edge along the
entire edge, past the other endpoint and ending at a random point
along an edge adjacent to that other endpoint. Randomly chose a new
reversal list of the third edge of the node so moved.
**Update 5x**- Similar to Update 5, but instead of replacing the entire reversal
list on the third edge, replace only an initial segment whose endpoint is
randomly chosen.
**Update 6**- Pick two distinct leaves and find the path between them. Choose a
random internal node along that path. Randomly choose a point in a
reversal list on a randomly chosen edge of the path and move the
node to that point, along with its third edge.
**Update 6x**- Similar to Update 6, but instead of replacing the entire reversal
list on the third edge, replace only an initial segment whose endpoint is
randomly chosen.
- Compose the beginning (signed) permutation with the inverse of the ending (signed) permutation. The problem of finding a reversal list between the beginning and ending permutation is reduced to finding a reversal list from this new permutation to the identity permutation.
- Convert this new signed permutation to an unsigned permutation and find the cycles and hurdles of the permutation.
- Classify all reversals as follows: Good reversals are proper reversals and reversals within a cycle of a hurdle. Neutral reversals are improper reversals whose endpoints are within the same cycle of the permutation. Poor reversals are all other reversals.

In several of the tree proposal algorithms, a list of reversals must be chosen that transforms one permutation into another. BADGER uses the following algorithm to randomly choose such reversals lists:

Begin with an empty list of reversals. If the beginning and ending
permutations are the same, then with probability
`prob-stop`

, which may be set in the run controls, return the current list of
reversals. Otherwise, or if the beginning and ending permutations differ,
choose a single reversal using the procedure described in the next paragraphs,
add the reversal to the list, apply it to the beginning permutation, and
repeat.

To choose one reversal, BADGER divides all possible reversals into three categories: good reversals, neutral reversals, and poor reversals. Good reversals are ones that are likely to transform the beginning permutation into one that is closer to the ending permutation as measured by the reversal distance. Neutral reversals are ones that are likely to leave the reversal distance unchanged. Poor reversals are likely to increase the reversal distances.

To categorize the reversals, BADGER performs the following steps:

After categorizing the reversals, BADGER selects one of the
categories with differing probabilities for each category, and then
uniformly chooses a reversal from that category. The probability of
choosing a good reversal is determined by the value of
`prob-good`

, and if the good reversal category is not
chosen, then the probability of choosing a neutral reversal is given
by `prob-neutral`

. Both of these values may be set in the
run controls.

To find a new segment of a reversal list, BADGER applies the parts of the reversal list that are to remain unchanged to the permutations in the nodes of the given edge to find the beginning and ending permutations for the segment. The above procedure is then applied.

If grouping is used, the tree
proposal algorithms will ensure that groups are maintained. To use
grouping and to set the groups, the run
controls `use-grouping`

and `group-list`

must be set.

The user may select which tree proposal algorithms are used by setting
the run control
`use-updates`

. There are some restrictions on when the
algorithms will run. Updates 3, 5, 5x, 6, and 6x require the data
to have four or more taxa; updates 1, 1x, and 4 require three or
more taxa; and updates 2 and 2x will run on two taxa trees. Should the data
have fewer than the necessary taxa, an algorithm will not be used
regardless of the run control.

Back to the table of contents.

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