Fast Walking Tree Method via Recurrence Reduction for Biological String Alignment

摘要

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 translocations 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 (～1 Mbps) to 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 duplicate computations can be looked up rather than re-computed, we are able to futher reduce the run time from quadratic to sub-quadratic.