Protein alignment: Exact versus approximate. An illustration

• Published in: Journal of computational chemistry 2015-05, Vol.36 (14), p.1069-1074
• Main Authors: Randić, Milan, Pisanski, Tomaž
• Format: Article
• Language: English
• Subjects: Algorithms; Amino Acid Sequence; Amino acids; Animals; BLAST; Comparative analysis; Databases, Factual; Humans; Mice; protein alignment; Proteins; Proteins - chemistry; Sequence Alignment - methods; sequential amino acid matrix; VESPA
• ISSN: 0192-8651; 1096-987X
• DOI: 10.1002/jcc.23892

We illustrate solving the protein alignment problem exactly using the algorithm VESPA (very efficient search for protein alignment). We have compared our result with the approximate solution obtained with BLAST (basic local alignment search tool) software, which is currently the most widely used for searching for protein alignment. We have selected human and mouse proteins having around 170 amino acids for comparison. The exact solution has found 78 pairs of amino acids, to which one should add 17 individual amino acid alignments giving a total of 95 aligned amino acids. BLAST has identified 64 aligned amino acids which involve pairs of more than two adjacent amino acids. However, the difference between the two outputs is not as large as it may appear, because a number of amino acids that are adjacent have been reported by BLAST as single amino acids. So if one counts all amino acids, whether isolated (single) or in a group of two and more amino acids, then the count for BLAST is 89 and for VESPA is 95, a difference of only six. © 2015 Wiley Periodicals, Inc. From the list of sequential labels for each adjacent pair of amino acid of two proteins one finds for all pairs of amino acids locations at which they have the same difference in labels. By ordering pairs having the same difference one finds segments at which two proteins have the same amino acids fragments. This information allows construction of the exact alignment of two proteins.