Biology Reference
In-Depth Information
the “longest” branch). When this branch is removed from
T
,it
divides the leaves of
T
into two subtrees. This decomposition is
repeated until every subtree has a small enough number of leaves, as
determined by the “maximum subproblem” size provided by the
user (this is one of the algorithmic parameters). Once every
subtree is small enough, the decomposition ceases, and each of
these subtrees defines a “subproblem” of sequences (associated to
the leaves of the subtree). The sequences in each subproblem are
realigned using a multiple sequence alignment method selected by
the user (the “aligner”), and the resulting subset alignments are
then merged into an alignment on the full set of sequences. This
merger step is handled by repeatedly applying an alignment
“merger” method (also specified by the user) in the reverse order
of the decomposition. Finally, a phylogenetic tree is estimated using
either RAxML or FastTree.
Each iteration of SAT
´
produces an alignment and tree, and thus
each SAT´ analysis produces a sequence of alignment/tree pairs
(one pair per iteration). Each alignment/tree pair has a maximum
likelihood (ML) score as well, which can help the user to select a tree
and alignment from the sequence of alignment/tree pairs. SAT
´
terminates the iterative process based on a user-specified termina-
tion condition, which can be either elapsed wall-clock time, or a
maximum number of iterations, or a lack of improvement in ML
score. The final alignment/tree pair output by SAT´ is chosen from
among the sequence of alignment/tree pairs generated during the
course of analysis, and can be the pair with the best maximum
likelihood score or the final pair produced by SAT
´
.
4 Algorithmic Parameters and Software Settings
The SAT´ algorithm specifies several algorithmic parameters, and
can be adapted to the needs of a particular dataset analysis by
changing these parameters. However, it can also be run in default
mode, so that the user does not need to set any parameters.
The software implementation of the SAT
´
algorithm provides
user-selectable settings for each of the algorithmic parameters.
Table
1
describes the relationship between the algorithmic para-
meters and software settings; additional discussion of these para-
meters (and guidance on how to set these parameters for improved
performance) is provided in the text.
After loading the input files in the SAT
´
program, the software
provides the option to automatically select all software settings based
upon the properties of the input dataset. The following sections
cover this usage scenario first, and we recommend the automatically
selected settings unless more advanced analyses are required.
Advanced usage scenarios involving changes to the automatically
selected software settings are discussed later in this chapter.
