Hacker News new | past | comments | ask | show | jobs | submit login

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.



Since I already had it open (for unrelated reasons), this might be relevant.

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.


But also:

> The Smith–Waterman algorithm is fairly demanding of time: To align two sequences of lengths m and n, O(mn) time is required.


Thankfully I'm only working with short sequences but yeah, I guess that might be a problem.


Agreed -- definitely worth thoroughly investigating this space to see whether there are any ideas that can be borrowed.




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: