heuristic pairwise alignment for
          transmembrane proteins.


  1. About hPATM
  2. Copyright notice
  3. Input description
  4. Output description
  5. Feedback
  6. References

1. About hPATM

The hPAFAG algorithm is based on the heuristic transformation of the Needleman & Wunsch and Smith & Waterman algorithms, featuring affine gap penalties. The heuristic transformation is based on two extra features:
This way transmembrane segments are anchored together*, allowing the pairwise alignment to "focus" on non-transmembrane segments.

*: not by force, but by more "strict" alignment

2. Copyright notice

All rights are reserved for the whole or part of the program. Permission to use, copy, and modify this software and its documentation is granted for academic use provided that authors are properly cited:

Zografos L.A.*, Promponas V.J., Hamodrakas S.J., Heuristic Pairwise alignment for Transmembrane Proteins, personal communication.
Department of Cell Biology and Biophysics, Faculty of Biology, University of Athens, Panepistimiopolis, Athens 15701, Greece


3. Input and options description

hPATM accepts the following type of input:

Sequences in FASTA format pasted in the dialog box (>name less than 6 characters). For example:
When a sequnce is submited in FASTA format, transmembrane segments, if they exist, should be declared explicitly in the dialog box below the sequence box, separating the number of the fisrt transmembrane aminoacid with the number of the last by a dash ('-'). Consecutive transmembrane segments must be separated by commas (','). For example:
hPATM has the following options:
  • Substitution matrix: the substitution matrix used for the alignment. Availiable options are BLOSUM62, PAM250, PHAT T70 B66 (suggested matrix BLOSUM62).

  • Gap opening penalty: the value of the gap opening penalty used in the affine gap introduction (suggested value 15).

  • Gap extension penalty: the value of the gap extension penalty used in the affine gap introduction (suggested value 3).

  • Heuristic bonus: the value added to the score when two transmembrane aminoacids are aligned. It is the base of the heuristic part of the algorithm. The Heuristic bonus value must not be too high (biased results) or too low (same results as global or local alignment). The value of the heuristic bonus must be somewhat larger (by 1 or 2) than the largest value of the substitution matrix (suggested value 12).

  • Heuristic penalty: the value substracted from the score when a gap is introduced in a transmembrane segment. This value is optionaly larger than 0 since the heuristic algorithm produces almost the same alignments even if the penalty value is set to greater than 0 (suggested value 0).

  • Type of alignment: Four types of alignment are availible:
    1. Heuristc Global Alignment: implemented by the hPATM algorithm, as a heuristic transformation of the Needleman & Wunsch algorithm (featuring affine gap).
    2. Heuristic Local Alignment: implemented by the hPATM algorithm as a heuristic transformation of the Smith & Waterman algorithm (featuring affine gap).
    3. Global Alignment: as implemented by the Needleman & Wunsch algorithm (featuring affine gap).
    4. Local Alignment: as implemented by the Smith & Waterman algorithm (featuring affine gap).
4. Output description

The output consists of a 'box', describing the options used for the alignment, the alignment's score and the sequences identity and similarity.

Note: in heuristic global or local alignment, the alignment score appears significantly higher due to the addition of the heuristic bonus.

###################*hPATM* ###################
#     *Preferences*:
#     matrix: blosum62, heuristic bonus: 12
#     gap opening: 15, gap extension:3, heuristic penalty: 0
#     *Scores*
#     sequence identity (ID) = 11.4942528735632%
#     sequence similarity (SI) = 27.8735632183908%

The alignment is printed in a linear format. Each line contains the sequence name and the alignend sequence. The lines above the first and below the second sequence (name followed by '_TM') highlight the transmembrane aminoacids with the letter 't'. The intervrning line (marked with 'cons') contains the consensus 'sequence'. Identitiesa re indicated by the aminoacid letter code or by '.' when aminoacid residues are similar (substitution matrix value > 0).

P02699_TM                               ttttttttttttt
cons                   .     A .  ...  Q .    ...L .
P02945_TM                                      tttttt

5. Feedback

Please send questions or feedback to lzografosgmail.com

6. References

  1. Needleman S.B. and Wunsch C. D. , A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol., 48:443--453, 1970.
  2. Smith T.F. and Waterman M.S. , Identification of Common Molecular Subsequences, J. Mol. Biol., 147:195-197, 1981.
  3. Gotoh O., An Improved Algorithm for Matching Biological Sequences, J. Mol. Biol., 162:705-708, 1982.
  4. Ng P.C., Henikoff J.G., Henikoff S., PHAT: a transmembrane-specific substitution matrix. Predicted hydrophobic and transmembrane. Bioinformatics. 2000 Sep;16(9):760-6.