title: FOGSAA: Fast Optimal Global Sequence Alignment Algorithm.
abstract: In this article we propose a Fast Optimal Global Sequence Alignment Algorithm, FOGSAA, which aligns a pair of nucleotide/protein sequences faster than any optimal global alignment method including the widely used Needleman-Wunsch (NW) algorithm. FOGSAA is applicable for all types of sequences, with any scoring scheme, and with or without affine gap penalty. Compared to NW, FOGSAA achieves a time gain of (70-90)% for highly similar nucleotide sequences (> 80% similarity), and (54-70)% for sequences having (30-80)% similarity. For other sequences, it terminates with an approximate score. For protein sequences, the average time gain is between (25-40)%. Compared to three heuristic global alignment methods, the quality of alignment is improved by about 23%-53%. FOGSAA is, in general, suitable for aligning any two sequences defined over a finite alphabet set, where the quality of the global alignment is of supreme importance.
authors.affiliation: Machine Intelligence Unit, Indian Statistical Institute, Kolkata, India.
authors.forename: Angana
authors.initials: A
authors.lastname: Chakraborty
authors.forename: Sanghamitra
authors.initials: S
authors.lastname: Bandyopadhyay
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D001483:Base Sequence; D004247:DNA / Q000737:chemistry / Q000235:genetics*; D011506:Proteins / Q000737:chemistry / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*
chemical_list: D011506:Proteins; D004247:DNA