Simplifying amino acid alphabets by means of a branch and bound algorithm and substitution matrices.
BACKGROUND
Protein and DNA are generally represented by sequences of letters. In a number of circumstances simplified alphabets (where one or more letters would be represented by the same symbol) have proved their potential utility in several fields of bioinformatics including searching for patterns occurring at an unexpected rate, studying protein folding and finding consensus sequences in multiple alignments. The main issue addressed in this paper is the possibility of finding a general approach that would allow an exhaustive analysis of all the possible simplified alphabets, using substitution matrices like PAM and BLOSUM as a measure for scoring.


RESULTS
The computational approach presented in this paper has led to a computer program called AlphaSimp (Alphabet Simplifier) that can perform an exhaustive analysis of the possible simplified amino acid alphabets, using a branch and bound algorithm together with standard or user-defined substitution matrices. The program returns a ranked list of the highest-scoring simplified alphabets. When the extent of the simplification is limited and the simplified alphabets are maintained above ten symbols the program is able to complete the analysis in minutes or even seconds on a personal computer. However, the performance becomes worse, taking up to several hours, for highly simplified alphabets.


BACKGROUND
AlphaSimp and other accessory programs are available at http://bioinformatics.cribi.unipd.it/alphasimp
Cannata
Nicola
N
CRIBI Biotechnology Centre, Universitá di Padova, via Ugo Bassi 58/B, Italy.
Toppo
Stefano
S
Romualdi
Chiara
C
Valle
Giorgio
G
D000465:Algorithms; D000595:Amino Acid Sequence; D003628:Database Management Systems; D030562:Databases, Protein; D003663:Decision Trees; D005069:Evaluation Studies as Topic; D016247:Information Storage and Retrieval / Q000379:methods*; D020407:Internet; D015233:Models, Statistical; D008969:Molecular Sequence Data; D011381:Programming Languages; D012680:Sensitivity and Specificity; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid; D012985:Software Design