high performance computing on graphics processing units: hgpu.org

Myers Fast Bit-Vector Algorithm for Approximate String Matching, further on referred as Myers algorithm only, is used to solve a string-matching problem in the informatics. String matching problems occurs if one text has to be compared with another text -a matching pattern or needle- for finding equalities, dissimilarities, or occurrences of this pattern in the text. This is often the case in practice if a part of a text needs to be found in documents, or databases, or to query internet search engines finding relevant or adjacent websites with the requested content. Consequently and in times of an ever faster information flow, reliable and fast algorithm are strongly engaged. These string-matching problems are distinguished into exact and approximate matching problems. The Myers algorithm solves an approximate string-matching problem, computing the distance of two texts. Approximate string matching is an important topic in fields of computational molecular biology also. One common problem is to align two sequences of DNA, RNA, or Proteins with each other to find their biological correlation or familiar relations. In praxis, this is used to match DNA probes for crime investigations, declaring paternity, or looking for specific genes occurrence in genomes to predict diseases for example, also called sequence alignments. Sequencing technologies in the second-generation can deliver DNA sequences with an unprecedented high throughput. Mapping the DNA pieces, the reads, to a mostly highly similar reference genome needs fast applicable algorithms. Usually this refers to read mapping methods.