Totally agreed. I'm not sure how to do the alignment scoring step in this case, perhaps some kind of DTW / FFT hybrid... definitely worth further consideration.
Unfortunately, I'm not too familiar with the current state of the art for whole-genome alignment, so I don't know for sure which algorithms are considered, but MUMmer4[1] seems like a good place to start. These algorithms are designed to handle sequences up to billions of letters long (e.g. the human genome, which is about 3 billion letters).
[1]: https://journals.plos.org/ploscompbiol/article?id=10.1371/jo...