N-dimensional Mapping of Amino Acid Substitution Matrices

Abstract

A procedure to map score matrices in n-dimensional spaces is presented. Score or substitutions matrices are used as similarity-like measure between amino acid in protein alignment procedures. The first stage of heuristic local alignments procedures as FASTA and BLAST uses local matching of very short sequences, also named k-tuples. By using L1 metric this matching task can be computed very fast. This procedure can be implemented by using SIMD instructions which are present in most of low cost microprocessors included in personal workstations and server. To design this procedure a table that maps the scores matrices as PAM y BLOSUM are needed. This table defines a representation of each amino acid residue in a n-dimensional space of lower dimensionality as possible; this is accomplished by using techniques of MDS as used in Pattern Recognition and Machine Learning. Previously, a distance function must be defined from the score matrix. To map the distance function a variation of the Sammon non-lineal dimensionality reduction procedure is used with a genetic algorithm that minimizes a goal function. To fit the SIMD constraints, both the dimension k of tuples and the space dimensionality n must verify: k ×n = 8×m. The table results for the BLOSUM62 with 1,2 and 4-dimensionality and graphical representations of the solution map are included. These last show that the biochemical amino acid groups are well mapped as data cluster; also the strong hydrophobic residues have a highlight spatial property, because there are linearly separable in 2-dimensional mapping.