FASTA

From Bioinformatikpedia
Revision as of 17:29, 17 August 2011 by Meier (talk | contribs) (Created page with "==Basic Information== {| style="float: right; border: 1px solid #BBB; margin: .46em 0 0 .2em;" ! Author | David J. Lipman, William R. Pearson |- ! Year | 1985 |- ! Reference | […")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Basic Information

Author David J. Lipman, William R. Pearson
Year 1985
Reference Rapid and sensitive protein similarity searches
Short description Alignment heuristic
Method

FASTA is one of the heuristics to sequence alignments.


Details

The algorithm works in four steps:

  • Identify regions of highest density in each sequence comparison: Searching for identical tuples (length 2) between the sequence and a look-up-table of the database. A match is declared, if a certain number of consecutive identical tuples (ktup-value) was found between two sequences. The matches can be visualized by diagonals in a matrix comparing two sequences. The best 10 local regions selected from all the diagonals put together are then saved.
  • Rescan the regions taken using the scoring matrices. trimming the ends of the region to include only those contributing to the highest score.
  • Optimal alignment of initial regions as a combination of compatible regions with maximal score.
  • Use a banded Smith-Waterman algorithm to calculate an optimal score for alignment.