Powtarzane uporządkowanej sekwencji algorytm wyszukiwania - algorytm, sekwencji, wyszukiwanie danych, programowanie dynamiczne, bioinformatyka

Mam dużą uporządkowaną sekwencję symboli, miliony symboli. Muszę znaleźć powtarzające się uporządkowane podsekcje, które:

1. Szukane podsekwencje są nieznane, muszę znaleźć podsekwencje, które powtarza się w innym miejscu dużej sekwencji.
2. Sekwencje mogą mieć różnice, takie jak obecność pewnej ilości szumu i brak niektórych symboli.

Niezbędny warunek:

3. Sekwencje mogą mieć niewielką ilość permutacji symboli sąsiadów.

Alfabet składa się z tysięcy symboli.

Czy możesz polecić dobrze znany i dobrze zbadany algorytm takiego zadania?

Odpowiedzi:

Możesz spróbować wielu wzorów aho-corasickdopasowanie i użyj symbolu wieloznacznego do wyszukiwania podciągów. Dla podciągów chcesz także odległość levensteina. Możesz spróbować mojej implementacji w PHP algorytmu aho-corasick z symbolem wieloznacznym at https://phpahocorasick.codeplex.com.