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.
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
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
prob-neutral. Both of these values may be set in the
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
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.