title: Improving sequence-matching algorithms by working from both ends.
abstract: Recent algorithms (e.g. Ukkonen, Fickett) align nucleic acid sequences (starting from the left) by bounding the allowed distance between subsequences by d, aligning, then incrementing d until all of both sequences are aligned. Aligning from both ends is more efficient. If the single-ended algorithm has computational cost CNk (C, k = constants; N = sequence length), the double-ended algorithm often has cost C(N/2)k.
mesh_terms: D001483:Base Sequence; D003201:Computers; D008433:Mathematics; D009696:Nucleic Acids
chemical_list: D009696:Nucleic Acids