Gap penalty

From Wikipedia, the free encyclopedia

Gap penalties are used during sequence alignment. Gap penalties contribute to the overall score of alignments, and therefore, the size of the gap penalty relative to the entries in the similarity matrix affects the alignment that is finally selected. Selecting a higher gap penalty will cause less favourable characters to be aligned, to avoid creating as many gaps.

Contents

[edit] Constant gap penalty

Constant gap penalties are the simplest type of gap penalty. The only parameter, d, is added to the alignment score when the gap is first opened. This means that any gap, receives the same penalty, what ever size it is.

[edit] Linear gap penalty

Linear gap penalties have only parameter, d, which is a penalty per unit length of gap. This is almost always negative, so that the alignment with fewer gaps is favoured over the alignment with more gaps. Under a linear gap penalty, the overall penalty for one large gap is the same as for many small gaps.

[edit] Affine gap penalty

Affine gap penalties attempt to overcome this problem. In biological sequences, for example, it is much more likely that one big gap of length 10 occurs in one sequence, due to a single insertion or deletion event, than it is that 10 small gaps of length 1 are made. Therefore, affine gap penalties are length dependent (unlike linear gap penalties which are length independent) and use a gap opening penalty, o, and a gap extension penalty, e. A gap of length l is then given a penalty o + (l-1)e. So that gaps are discouraged, o and e are almost always negative. Furthermore, because a few large gaps are better than many small gaps, e is almost always smaller than o to encourage gap extension rather than gap introduction.

[edit] Further reading

  • Taylor WR, Munro RE (1997). Multiple sequence threading: conditional gap placement. Fold Des, 2(4):S33-9.
  • Taylor WR (1996). A non-local gap-penalty for profile alignment. Bull Math Biol, 58(1):1-18.
  • Vingron M, Waterman MS (1994). Sequence alignment and penalty choice. Review of concepts, case studies and implications. J Mol Biol, 235(1):1-12.
  • Panjukov VV (1993). Finding steady alignments: similarity and distance. Comput Appl Biosci, 9(3):285-90.
  • Alexandrov NN (1992). Local multiple alignment by consensus matrix. Comput Appl Biosci, 8(4):339-45.
  • Hein J (1989). A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given. Mol Biol Evol, 6(6):649-68.
  • Henneke CM (1989). A multiple sequence alignment algorithm for homologous proteins using secondary structure information and optionally keying alignments to functionally important sites. Comput Appl Biosci, 5(2):141-50.
  • Reich JG, Drabsch H, Daumler A (1984). On the statistical assessment of similarities in DNA sequences. Nucleic Acids Res, 12(13):5529-43.