High Speed Searching Possible with Jazzy Algorithm
May 16, 2012
The first in a series where the official Avadis NGS blog describes algorithms used in their product, “Elegant Exact String Match Using BWT” explains a fast algorithm used to perform an exact string match. The article acknowledges that many readers want to know why they needed another string matching algorithm.
Summarizing the problem, the article informs us that the issue lies in the need to matchworks billions of short strings to a 3 billion character long text. Currently, the way sequencing technology works is too convoluted.
The article continues:
“We need an algorithm that allows repeatedly searching on a text as fast as possible. We are allowed to perform some preprocessing on the text once if that will help us achieve this goal. BWT search is one such algorithm. It requires a one-time preprocessing of the reference to build an index, after which the query time is of the order of the length of the query (instead of the reference).”
Overall, the article does a solid job providing the contextual technology revolving around their product and explaining it with diagrams and concise language. It is a recommended read for those who would like to know more about this interesting idea for high speed searching.
Megan Feil, May 16, 2012
Sponsored by PolySpot