How I Wrote an Ultra-Fast DNA Sequence Alignment Algorithm in JavaScript

Re:How I Wrote an Ultra-Fast DNA Sequence Alignment Algorith... by tstactplsignore on Monday February 23, 2015 @02:31PM (#9096430)

This is a neat JS library with some possible applications, but if you're only matching substrings without gaps, then you're basically string searching, not performing alignment. Alignment is an entirely different and more complicated computational problem with decades of algoritm development (see Smith-Waterman, Needleman-Wunsch, Burrows-Wheeler transform) and implementation going into it, and it is far more biologically useful and practical than substring searching. Considering this, in practice heuristic implementations like BLAST, FASTA, and lastz are used to do most big alignment searching, and that's not even considering multiple sequence alignment, which is another problem into itself. In other words, it's a useful JS library and interesting implementation, but it isn't alignment.

[ Parent | on HN ]

Re:How I Wrote an Ultra-Fast DNA Sequence Alignment Algorith... by keithwhor on Monday February 23, 2015 @02:37PM (#9096469)

The algorithm maps every position of seqSearch to seqGenome, aggregates the results, and returns them. It is not merely a string search. (If it were, the Booyer-Moore [1] algorithm would outperform this significantly, binary or not, and we'd call it a day.) It is aligning seqSearch to seqGenome and returning the best results, in order.

Alignment is not restricted to "gapped" alignments only (or there wouldn't be a need for such a distinction!).

You can modify the algorithm to include gapped alignments (by introducing gaps in your search sequence), as it supports a "gap" character ("-"). The gap character will just always count as "not a match."

[1] http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sear...

[ Parent | on HN ]

Re:How I Wrote an Ultra-Fast DNA Sequence Alignment Algorith... by tstactplsignore on Monday February 23, 2015 @02:53PM (#9096560)

So, ungapped alignment is just substring searching with degeneracy, which is fine. While that is its own computational problem and may even have the occasional biological application, sequence alignment is defined as a gapped alignment problem (see the Wikipedia page, for example [1], which defines gap insertion as a critical step, and all alignment variants on the page are gapped alignments)

I am not sure you understand what gapped alignment is- it is not the alignment of a sequence with known gaps, but an algorithm which determines the best placement of gaps in a query sequence to obtain the highest matching score. This is a very different problem than the one you just described, and is essentially "the hard part" of sequence alignment. [1] http://en.m.wikipedia.org/wiki/Sequence_alignment

[ Parent | on HN ]

Re:How I Wrote an Ultra-Fast DNA Sequence Alignment Algorith... by mbreese on Monday February 23, 2015 @03:00PM (#9096605)

See here: https://news.ycombinator.com/item?id=9096064

Turns out they aren't actually after an alignment per se, but rather trying to match a DNA binding motif.

(You're right though about this not being an alignment, rather just a substring search with degeneracy).

[ Parent | on HN ]

Re:How I Wrote an Ultra-Fast DNA Sequence Alignment Algorith... by keithwhor on Monday February 23, 2015 @03:40PM (#9096865)

Hmm, while I understand the problem of gapping is traditionally the hard part, I'm under the impression that the argument you're putting forward is primarily one of semantics.

"In bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences." (From the article you linked.)

Gapped sequence alignment is certainly far more robust (and biologically relevant - insertions are a common error - when comparing sequences across organisms) than ungapped, and a much harder problem, but as for the definition of "alignment" itself, I don't believe I've misnamed anything here.

If we're going to be overly pedantic about the use of the word "alignment" that's fine, but I'm not sure it's a worthwhile debate to have. A quick search for "ungapped sequenced alignment" returns a great deal of results on Google [1]. So if I am mistaken, I'm certainly not the first (nor do I believe I'll be the last.)

Furthermore, there's nothing preventing anybody from using the methods described here from implementing an ungapped sequence alignment tool that outperforms tools that only use string comparisons. :)

[1] https://www.google.com/search?q=ungapped%20sequence%20alignm....

[ Parent | on HN ]

Re:How I Wrote an Ultra-Fast DNA Sequence Alignment Algorith... by lightlike on Monday February 23, 2015 @05:05PM (#9097356)

you shouldn't dismiss this as an argument over semantics if your understanding of the term differs from researchers' use of the term. if you introduce "a fast tool for XYZ" and researchers understand XYZ to mean A, where you understand it to mean B, then the tool is not useful for researchers to perform what they know as XYZ.

tools like BLAST are extremely sophisticated and have been under development for decades, and I'm fairly confident they've moved past naive string comparisons by now.

[ Parent | on HN ]

Re:How I Wrote an Ultra-Fast DNA Sequence Alignment Algorith... by keithwhor on Monday February 23, 2015 @06:08PM (#9097655)

Fair. Though I'm not convinced "ungapped sequence alignment" is particularly confusing to a researcher, considering there are tools and papers that have existed for decades using this description [1][2][3]. Though the algorithm described in my article is extremely focused on raw performance (and relatively naive with scoring), I would still choose to categorize it as primarily a tool that deals with ungapped sequence alignment, specifically supporting IUPAC degenerate nucleotide sequences. Thus, I believe the initial argument is, indeed, overly pedantic.

And to be clear, nowhere am I comparing what I've developed to BLAST. (They have very different applications.)

[1] http://schneider.ncifcrf.gov/paper/malign/

[2] http://www.ncbi.nlm.nih.gov/pubmed/9697204

[3] http://www.ncbi.nlm.nih.gov/pubmed/15130540

[ Parent | on HN ]