Biology Reference
In-Depth Information
2. An alignment is said global when internal and terminal gaps are
not distinguished, whereas said semi-global when the terminal
gaps are not penalized. Global and semi-global alignments are
obtained with nearly the same dynamic programming algo-
rithms except for the initial conditions and the choice of the
traceback point [
107
].
3. Sometimes slightly different definition of gap open penalty is
used:
g
ð
k
Þ¼
a
þ
bk
ð
1
Þ
. It is easy to see that
a
¼
(
u
+
v
)
u
.
4. The original formulation [
18
] considers only aligned pairs
ignoring gaps, which can lead to over prediction of aligned
pairs. By taking into account of the probabilities of
P
(
a
i
~ '-')
and
P
('-' ~
b
j
), a better balance between sensitivity and speci-
ficity may be achieved [
20
]. For more detailed discussion about
the balance between sensitivity and specificity,
see
[
108
].
and
b
¼
Acknowledgment
I thank Dr. Kentaro Tomii for instruction about protein fold
recognition methods. This work was partly supported by Kakenhi
(Grant-in-Aid for Scientific Research) B (grant number 22310124)
from the Ministry of Education, Culture, Sports, Science and Tech-
nology of Japan.
References
1. Carrillo H, Lipman D (1988) The multiple
sequence alignment problem in biology.
SIAM J Appl Math 48:1073-1082
2. Gupta SK, Kececioglu JD, Schaffer AA
(1995) Improving the practical space and
time efficiency of the shortest-paths approach
to sum-of-pairs multiple sequence alignment.
J Comput Biol 2:459-472
3. Kawashima S, Pokarowski P, Pokarowska M,
Kolinski A, Katayama T, Kanehisa M (2008)
AAindex: amino acid index database, progress
report
symposium on biocomputing. World Scien-
tific, Singapore, pp 115-126
6. Frith MC, Hamada M, Horton P (2010)
Parameters for accurate genome alignment.
BMC Bioinformatics 11:80
7. Needleman SB, Wunsch CD (1970) A general
method applicable to the search for similari-
ties in the amino acid sequence of two pro-
teins. J Mol Biol 48:443-453
8. Sellers PH (1974) On the theory and compu-
tation of evolutionary distances. SIAM J Appl
Math 26:787-793
9. Waterman MS, Smith TF, Beyer WA (1976)
Some biological sequence metrics. Adv Math
20:367-387
10. Gotoh O (1982) An improved algorithm for
matching biological sequences. J Mol Biol
162:705-708
11. Gotoh O (1990) Optimal sequence align-
ment allowing for long gaps. Bull Math Biol
52:359-373
12. Waterman MS, Byers TH (1985) A dynamic-
programming algorithm to find all solutions
2008. Nucleic Acids Res
36:
D202-D205
4. Dayhoff MO, Schwartz RM, Orcutt BC
(1978) A model of evolutionary change in
proteins. In: Dayhoff MO (ed) Atlas of pro-
tein sequence and structure, vol 5, Suppl. 3.
National Biomedical Research Foundation,
Silver Spring, MD, pp 345-352
5. Chiaromonte F, Yap VB, Miller W (2002)
Scoring pairwise genomic sequence align-
ments. In: Altman RB, Dunker AK, Hunter
L, Klein TED, Lauderdale K (eds) Pacific
