This is a test version of Biostars. For the public version, visit https://www.biostars.org.
What Kinds Of Efficient Algorithms Can Be Used To Correct Read Errors

This error correction problem caught my eye. Is there an O(n) algorithm for this, where n is the number of reads? There's the relatively straightforward O(n2) method of checking all the pairs, but I'm wondering if there's something better out there.

sequencing error read
• 2,508 views • link
updated by jts jts • written by Snowball • Snowball

Forgive my ignorance, but I am not aware of the "O" term in the algorithm you mention, can you give us some more information on this method?

• 0 views • link
written by Josh Herr Josh Herr

big O notation is just a way to describe how an algorithm performs given an input. You can read more about it here: http://en.wikipedia.org/wiki/Big_O_notation

For example, looking for an element in a dictionary/hash structure would be O(1) because you can directly access it in one operation. Whereas a primitive search algorithm where you iterate through an entire list of elements to find a specific element would be O(n) where n is the number of members in the list. A binary search tree where you effectively reduce your search space by 1/2 every node would give you O(logN) processes.

It's basically a way to describe the performance of an algorithm

• 89 views • link
written by Damian Kao Damian Kao

+1 and thanks Damian! I come from a more strictly biological background so I need a little help with things sometimes.

• 0 views • link
written by Josh Herr Josh Herr

1 answer

k-mer based error correction is much faster than overlap based methods. The complexity is effectively O(N) where N is the total number of bases. See the quake paper for a representative approach. Many other programs use a similar approach.

• 57 views • link
written by jts jts

Log in to answer this question.

More posts like this