Biology Reference
In-Depth Information
propagated into subsequent alignment steps (“Once a gap, always a
gap”) [
3
]. Several methods exist that try to alleviate the greediness
of the progressive alignment, for example by implementing an
iterative alignment protocol, as first proposed by Hogeweg and
Hesper [
2
].
Profile ALIgNmEnt (PRALINE) adopts a global progressive
alignment algorithm that reevaluates at each alignment step which
sequence or sequence block pairs to align. This means that unlike
many other progressive MSA methods [
2
,
4
-
6
], PRALINE deter-
mines at each step during progressive alignment which alignment
between any alignment block or hitherto unaligned sequence will
be optimal such that a tree reflecting the order in which sequences
are aligned is produced on the fly without the use of a precalculated
guide tree.
In order to minimize the effects of the greediness of the pro-
gressive alignment protocol and to improve alignment quality,
PRALINE includes a number of alignment strategies to improve
the basic progressive protocol: global profile preprocessing,
homology-extended alignment, secondary structure-guided align-
ment, and transmembrane (TM)-aware alignment. It also allows
combinations of different strategies to cater for the various needs
researchers might have, for example combining profile preproces-
sing with secondary structure-guided alignment or with TM-aware
alignment.
PRALINE employs various profile preprocessing protocols to
address the problems caused by the greediness of progressive align-
ment method. These protocols can be categorized into three types:
global, local, and homology-extended profile preprocessing [
7
,
8
].
The main principle behind these profile preprocessing techniques is
avoiding early error in progressive alignment by projecting infor-
mation from other sequences onto each input sequence prior to
progressive alignment. This is done by converting each input
sequence into a pre-profile, which is abstracted from a master-slave
sequence alignment of the sequence considered with the other
input sequences. In the global preprocessing strategy, sequences
are stacked upon the key sequence, i.e., the sequence considered, by
means of global alignment, while in the local preprocessing proto-
col, local alignments are used to enrich the information of the key
sequence. The homology-extended multiple alignment strategy is
an extension of the local preprocessing method. In this method,
information to enrich the input sequences is not gleaned from
other input sequences, but from putatively homologous sequences
residing in sequence databases. It has been shown in previous
studies that the addition of homology information has distinctly
positive effects on alignment quality, particularly in cases of dis-
tantly related protein sets [
8
-
11
].
PRALINE provides the option to allow the incorporation of
secondary structure and/or transmembrane information to guide
