4 ms·
You should look into DNA and RNA sequence alignment algos for possible improvements on your FFT. It's a huge and very well-explored space.
by psychometry 8y ago
You should look into DNA and RNA sequence alignment algos for possible improvements on your FFT. It's a huge and very well-explored space.
- zimpenfish 8y agoSince I already had it open (for unrelated reasons), this might be relevant. https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit... > The Smith–Waterman algorithm performs local sequence alignment; that is, for determining similar regions between two strings of nucleic acid sequences or protein sequences.
- amelius 8y agoBut also: > The Smith–Waterman algorithm is fairly demanding of time: To align two sequences of lengths m and n, O(mn) time is required.
- zimpenfish 8y agoThankfully I'm only working with short sequences but yeah, I guess that might be a problem.
- smacke 8y agoAgreed -- definitely worth thoroughly investigating this space to see whether there are any ideas that can be borrowed.