Reconstruction of genuine pair-wise sequence alignment.
In many applications, the algorithmically obtained alignment ideally should restore the "golden standard" (GS) alignment, which superimposes positions originating from the same position of the common ancestor of the compared sequences. The average similarity between the algorithmically obtained and GS alignments ("the quality") is an important characteristic of an alignment algorithm. We proposed to determine the quality of an algorithm, using sequences that were artificially generated in accordance with an appropriate evolution model; the approach was applied to the global version of the Smith-Waterman algorithm (SWA). The quality of SWA is between 97% (for a PAM distance of 60) and 70% (for a PAM distance of 300). The percentage of identical aligned residues is the same for algorithmic and GS alignments. The total length of indels in algorithmic alignments is less than in the GS-mainly due to a substantial decrease in the number of indels in algorithmic alignments.
Polyanovsky
Valery
V
Engelhardt Institute of Molecular Biology, Russian Academy of Science (RAS), Moscow, Russia.
Roytberg
Mikhail A
MA
Tumanyan
Vladimir G
VG
D000465:Algorithms; D019143:Evolution, Molecular; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA; D020539:Sequence Analysis, Protein; D017423:Sequence Analysis, RNA