Fast walking tree method via recurrence reduction for biological string alignment
By: Tai Hsu and Paul Cull.
Contributors: Cull, Paul, 1943-; Oregon State University. Dept. of Computer Science.
Series: TR -- 02-20-02.; Technical report (Oregon State University. Dept. of Computer Science) -- 02-20-02.
Publisher: Oregon State University, Dept. of Computer Science
Published: 2002
Place of publication: [Corvallis, OR
Language: eng
Subjects: Matching theory.; Genetics -- Data processing.; Graphical user interfaces (Computer systems); Heuristic programming.
Description: The meaning of biological sequences is a central problem of modern biology. Although string matching is well understood in the edit-distance model, biological strings with transpositions and inversions violate this model's assumptions. To align biologically reasonable strings, we proposed the Walking Tree Method, an approximate string alignment method that can handle insertion, deletions, substitutions, translocations, and more than one level of inversions. Our earlier versions were able to align whole bacterial genomes (approx.1 Mbps) and discover and verify genes. As extremely long sequences can now be deciphered rapidly and accurately without amplification, speeding up the method becomes necessary. Via a technique that we call it "recurrence reduction" in which same computations can be looked up rather than recomputed, we are able to significantly improve the performance, e.g., 400% for 1-million base pair alignments.
Notes: Caption title.

"May 2002."

Includes bibliographical references (leaves [6]-[7]).

Also available on the World Wide Web.