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.