BADGER

Bayesian Analysis to Describe Genomic Evolution by Rearrangement

Version 1.02 beta, June 11, 2004

Algorithms

Tree representation

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.

Tree proposal algorithms

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

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

Finding new reversal lists

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:

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.

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.

Algorithms when grouping is used

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.

Selecting algorithms

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.

badger@badger.duq.edu