So I am a computer science student and I was recently looking at the subject of comparing DNA sequences. Probably the most widely used algorithm is the Needleman-Wunsch algoirithm and while it might be suitable for most cases, It bothers me that an $O(n^2)$ algorithm is used to compare large batches of text, both from the time and required space perspective. The space requirement bothers me the most, considering the number of nucleotides that need to be compared in a typical application, taking up gigabytes if not more memory.

Although some improvements are made to the algorithm, making it up to 80% faster (the FOGSAA algorithm) I still think that I am missing something. Are there any algorithms for this problem that run faster than $O(n^2)$ asymptotically? From the application perspective - are non-square algorithms used in the field? I was thinking suffix trees might be useful for this but as far as I know they are only used for sequencing, not comparing sequences.

  • $\begingroup$ $O(n^2)$ is indeed too much in practice. There are a lot of practical tools for efficient sequence alignment, you can google them. $\endgroup$
    – user114966
    Mar 31, 2021 at 13:48
  • $\begingroup$ Thank you @Dmitry, but I am not looking for a tool, I would like to understand the principles of such methods. $\endgroup$ Mar 31, 2021 at 13:50
  • $\begingroup$ I thought it would be simple to find which tool uses which algorithm, but for Clustal it turned out to be rather painful. It seems that Clustal (at least its earlier version) uses algorithm from "Rapid similarity searches of nucleic acid and protein data banks" $\endgroup$
    – user114966
    Mar 31, 2021 at 14:06
  • $\begingroup$ @Dmitry thank you! I will look into that paper, and I will post if I find anything of interest. $\endgroup$ Apr 1, 2021 at 20:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.