Local Sequence Alignment FASTA Local Sequence Alignment Against a Database Problem

Local Sequence Algignment. The local sequence alignment problem is de-fined as follows: Given two strings S = s1... sn and T = t1... tm, a substitution matrix Score and an insertion/deletion penalty δ, find a pair of substrings si... si+k of S and tj... tj+l of T that have the best overall alignment score, and return the best alignment for them. Local Sequence Algignment against a database. The local sequence alignment against a database problem extends the local sequence alignment prob-lem by introducing multiple strings against which a single query string is a aligned: Given a query string S = s1... sn, and a collection of strings D = {D1,...DM} (usually referred to as a sequence database), a substi-tution matrix Score and an insertion/deletion penalty δ, find the best local alignments of S with any/all strings from D. Note. Smith-Waterman algorithm for local sequence alignment has runtim