Improving sequence-matching algorithms by working from both ends.
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.
D001483:Base Sequence; D003201:Computers; D008433:Mathematics; D009696:Nucleic Acids
D009696:Nucleic Acids