FASTA
From Bioinformatikpedia
Basic Information
| Author | David J. Lipman, William R. Pearson |
|---|---|
| Year | 1985 |
| Reference | Rapid and sensitive protein similarity searches |
| Short description | Alignment heuristic |
| Method | look-up table & agglomerative alignment |
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.
