Overview
This lecture focuses on the major sequence alignment algorithms in bioinformaticsтАФFAST and BLASTтАФand their applications.
Pairwise and Multiple Sequence Alignment
- Pairwise alignment compares two sequences to align them based on matches, mismatches, and gaps.
- Multiple sequence alignment involves several sequences, aligning them sequentially by adding one sequence at a time.
- Alignments can be of two types: global (full sequence alignment) and local (partial sequence alignment).
Global and Local Alignment
- Global alignment: The best alignment between two entire sequences is done using the Needleman-Wunsch algorithm.
- Local alignment: Alignment of parts of sequences, comparing smaller sequences with larger ones or databases, using the Smith-Waterman algorithm.
- Local alignment is used in tools like BLAST.
History of Sequence Alignment Algorithms
- 1970: Needleman-Wunsch (global alignment)
- 1981: Smith-Waterman (local alignment)
- 1988: FASTA algorithm (by Pearson and Lipman)
- 1990: BLAST algorithm (improvement on FASTA)
- 1995 and beyond: Various versions of BLAST (such as Megablast) were developed
FASTA and BLAST Algorithms
- FASTA was the first fast sequence search algorithm that allowed quick comparison of query sequences in a database.
- BLAST is a modified and faster version of FASTAтАФsimpler, more user-friendly, and statistically more robust.
- Both algorithms focus on finding small, exact matching segments.
- Three stages of the algorithm: identifying small exact matches, extending them, and then optimizing the best hits.
Key Terms & Definitions
- Alignment тАФ Matching of two or more sequences (similarity/difference).
- Global Alignment тАФ Alignment of entire sequences.
- Local Alignment тАФ Alignment of parts of sequences.
- FASTA тАФ The first fast sequence search algorithm.
- BLAST тАФ Basic Local Alignment Search Tool; a faster and more effective search tool.
- Algorithm тАФ A step-by-step method for solving problems.
Action Items / Next Steps
- In the next class, engage in practical study of FASTA and BLAST algorithms.
- Practice with tools related to sequence alignment.