Difference between revisions of "FASTA"

From Bioinformatikpedia
(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 | […")
 
Line 15: Line 15:
 
|-
 
|-
 
! Method
 
! Method
  +
| look-up table & agglomerative alignment
|
 
 
|}
 
|}
   
 
FASTA is one of the heuristics to sequence alignments.
 
FASTA is one of the heuristics to sequence alignments.
  +
  +
  +
  +
   
   

Revision as of 17:30, 17 August 2011

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.