This sounds very similar to the problem of whole-genome alignment in bioinformatics. You have, say, the human and chimp genome sequences, and you want to align

This sounds very similar to the problem of whole-genome alignment in bioinformatics. You have, say, the human and chimp genome sequences, and you want to align them to find out which portions of each genome correspond to which portions in the other, allowing for the possibility of insertions or deletions of DNA sequences in each one. 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/journal.pcbi.1005944 https://journals.plos.org/ploscompbiol/article?id=10.1371/jo...