This is a test version of Biostars. For the public version, visit https://www.biostars.org.
String matching algorithms of biological sequences

Hi,

I would like test accuracy, speed of some basics string matching algorithm on biological sequence. Where can i find a good library (python, c, c#, ... whatever) with implementation of string matching algorithm or service on the web? Do you have something that would help me, advise, ...?

sequence genome gene
• 4,480 views • link
written by markic • markic

Whats wrong with strstr, or grep‽

• 0 views • link
written by kloetzl kloetzl

Nothing, but i need more algorithms with scientific approach and compare them on different data sets.

• 0 views • link
written by markic • markic

I am predicting, it will be hard to beat strstr or pcmpestri unless you do some precomputation on the haystack (suffixtree etc.).

• 0 views • link
written by kloetzl kloetzl

Do you have python library?

• 0 views • link
written by markic • markic

3 answers

EXACT STRING MATCHING ALGORITHMS / Christian Charras - Thierry Lecroq : http://www-igm.univ-mlv.fr/~lecroq/string/ "Brute Force algorithm Deterministic Finite Automaton algorithm Karp-Rabin algorithm Shift Or algorithm Morris-Pratt algorithm Knuth-Morris-Pratt algorithm Simon algorithm Colussi algorithm Galil-Giancarlo algorithm Apostolico-Crochemore algorithm Not So Naive algorithm Boyer-Moore algorithm Turbo BM algorithm Apostolico-Giancarlo algorithm Reverse Colussi algorithm Horspool algorithm Quick Search algorithm Tuned Boyer-Moore algorithm Zhu-Takaoka algorithm Berry-Ravindran algorithm Smith algorithm Raita algorithm Reverse Factor algorithm Turbo Reverse Factor algorithm Forward Dawg Matching algorithm Backward Nondeterministic Dawg Matching algorithm Backward Oracle Matching algorithm Galil-Seiferas algorithm Two Way algorithm String Matching on Ordered Alphabets algorithm Optimal Mismatch algorithm Maximal Shift algorithm Skip Search algorithm KMP Skip Search algorithm Alpha Skip Search algorithm"

and their implementations in C...

• 0 views • link
written by Pierre Lindenbaum Pierre Lindenbaum

Thought this was spam (Dawg matching algorithm?) before I saw the embedded link :-)

• 0 views • link
written by GenoMax GenoMax

Do these algorithms work properly?

• 0 views • link
written by markic • markic

Have a look on seqan c++ library. http://seqan.readthedocs.io/en/master/

For instance, it uses 2 bits per nucleotides instead 8 used by plain text sequence.

• 0 views • link
written by sacha sacha

Thanks. I will try this. It seems good and easy to use.

• 0 views • link
written by markic • markic

You may have interest to take a look at the source code of MutScan.

MutScan is based on DNA sequence string matching algorithm, and it can detect and visualize target mutations by scanning FastQ files directly.

• 0 views • link
written by chen chen

Thanks. If you have any good library please send it to me.

• 0 views • link
written by markic • markic

Sorry, but I don't have a library for that.

• 0 views • link
written by chen chen

Log in to answer this question.

More posts like this