Fast walking tree method via recurrence reduction for biological string alignment Public Deposited

http://ir.library.oregonstate.edu/concern/technical_reports/n009w3549

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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 [4,5,6,7,8], 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) and discover and verify genes. As extremely long sequences can now be deciphered rapidly and accurately without amplification [2,3,15], 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.
Resource Type
Date Available
Date Issued
Series
Keyword
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Submitted by Laura Wilson (laura.wilson@oregonstate.edu) on 2012-02-27T23:47:48Z No. of bitstreams: 1 Fast walking tree method via reccurence reduction for biological string alignment.pdf: 163118 bytes, checksum: 0f48bc22c250157e54f8956c404fe3ff (MD5)
  • description.provenance : Approved for entry into archive by Laura Wilson(laura.wilson@oregonstate.edu) on 2012-02-27T23:48:55Z (GMT) No. of bitstreams: 1 Fast walking tree method via reccurence reduction for biological string alignment.pdf: 163118 bytes, checksum: 0f48bc22c250157e54f8956c404fe3ff (MD5)
  • description.provenance : Made available in DSpace on 2012-02-27T23:48:55Z (GMT). No. of bitstreams: 1 Fast walking tree method via reccurence reduction for biological string alignment.pdf: 163118 bytes, checksum: 0f48bc22c250157e54f8956c404fe3ff (MD5) Previous issue date: 2002

Relationships

In Administrative Set:
Last modified: 07/18/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items