Najczęstsze następstwa

Łańcuch ma podsekwencje, ale zwykle nie wszystkie są odrębne. Jaka jest złożoność znalezienia maksymalnej częstotliwości dowolnego podsekwencji? $2^n$

Na przykład ciąg „podsekwencja” zawiera 7 kopii podsekwencji „sue” i jest to maksimum.

Przykładowy kod brute-force na stronie http://ideone.com/UIp3t

Czy istnieją powiązane twierdzenia strukturalne? Oba okazują się fałszywe :

najdłuższa z podsekwencji o maksymalnej częstotliwości jest unikalna
maksymalna częstotliwość dowolnej podsekwencji jest jednomodalna w $k$ $k$

Ewentualnie powiązane linki:

Zliczanie # odrębnych podciągów http://11011110.livejournal.com/254164.html $\in \mathbf{P}$
Powiązany problem konkursowy dla wielu źródeł http://www.spoj.pl/problems/CSUBSEQS/
Powiązany dokument http://dx.doi.org/10.1016/j.tcs.2008.08.035

Edytuj 10 dni później: dzięki za obejrzenie! Zastanawiałem się, czy może to stanowić miły problem w rozwiązaniu programistycznym w czasie wielomianowym. Chyba nie, ale mam nadzieję, że pomyślę o tym później.

ds.algorithms string-search daveagp
źródło

Być może naiwne początkowe pytanie: czy jasne jest, że ten problem dotyczy nawet NP ? To znaczy: w przypadku problemu z ustaleniem, czy istnieje podsekwencja z przynajmniej k wystąpieniami w ciągu n -znaków, jak wyglądałby certyfikat? Na przykład, wykaz wszystkich krotek indeksów wskazujących instancje danego podsekwencji nie byłby wielomianowy dla łańcucha aaa ... aa (który, choć jest nudnym wejściem, ma jednak podciąg z grubsza wystąpienia).

n C (n / 2)

$n \mathbf C (n/2)$

Niel de Beaudrap,

@Niel de Beaudrap: Myślę, że możemy policzyć liczbę wystąpień jako podsekwencje w czasie wielomianowym przez programowanie dynamiczne, dzięki czemu możliwe jest użycie samej podsekwencji jako certyfikatu.

Tsuyoshi Ito

Jestem trochę zdezorientowany: czy pytanie „biorąc pod uwagę ciąg znaków, znaleźć podsekwencję, która występuje maksymalną liczbę razy?”

Suresh Venkat

@SureshVenkat: Tak, to moje zrozumienie. Na przykład, biorąc pod uwagę sekwencję X jako dane wejściowe, poprawną odpowiedzią byłaby sekwencja X.

n

$n$

n / 2

$n/2$

Jeffε

@ marzio-de-biasi: pytanie, z którym się łączysz, jest inne (i znacznie łatwiejsze): otrzymujesz podsekwencję.

David

Odpowiedzi:

z wyszukiwania, oto artykuł z niektórymi badaniami i ustaleniami dotyczącymi badań na poziomie absolwentów, ale (zastrzeżenie) bez referencji. ma pewne heurystyki, szacunki, wyniki empiryczne i komentarze na temat problemu oraz kilka pomysłów na udowodnienie jego (przybliżenia) złożoności itp.

Identyfikacja najczęstszych następstw
CSE 549 Computational Biology Project Raport końcowy
Mikhail Bautin 2006

(chociaż istnieją pewne standardowe problemy dotyczące podsekwencji, które są nieco podobne i badane, np. w pracy Elzinga i in., czy jest możliwe, że ten konkretny problem podsekwencji nie był zbytnio badany?)

vzn
źródło

Nie rozumiem, dlaczego zostało to odrzucone. Być może nie jest to bardzo głęboka praca, ale wydaje się, że dotyczy bezpośrednio tematu.

David Eppstein,

fyi / addendum Bautin mówi również na końcu artykułu, że ma 5 000 wierszy kodu C ++ i języka Python na temat problemu / papieru dla każdego zainteresowanego

@David, nie sądzę, że głosowanie negatywne wynika z powiązanego papieru, prawdopodobnie ma to raczej związek z faktem, że ta odpowiedź wygląda (zasadniczo) jako odpowiedź w jednym wierszu (bez wyjaśnienia, w jaki sposób artykuł jest powiązany z pytaniem i odpowiada). To może być bardziej odpowiednie jako komentarz.

Kaveh

ok kaveh, więc przeliterowane: gazeta wydaje się ujawniać (chyba że ktoś sam może znaleźć lepszą referencję lub sam wymyślić dowód tego trudnego problemu), że dokładna złożoność problemu jest jak dotąd nieznana / otwarta (inna niż oczywista PSpace / ExpTime) i może zawierać najbardziej znane analizy / podejścia do jego rozwiązania do tej pory

dniu

Znalazłem ten artykuł wcześniej i przepraszam, że nie odsyłam do niego powyżej, ponieważ nie sądziłem, że zawiera wiele konkretnych informacji. Jakiś czas temu wysłałem do autora wiadomość e-mail z pytaniem, czy mógł coś jeszcze powiedzieć o wszystkim, co się wydarzyło od czasu jego napisania, ale nie otrzymałem jeszcze odpowiedzi.

daveagp

Nie odpowiedź, tylko lemat.

Przede wszystkim można się zastanawiać, co jest najczęstszym podciągiem ciągów takich jak 12..t12..t12..t .. Po krótkim zastanowieniu zdajemy sobie sprawę, że musi mieć również postać 12..t12..t12 .., po prostu oczywiście krótszą. Jeśli oryginalny ciąg ma długość nt, a podsekwencja tej specjalnej formy ma długość k, liczba jego wystąpień wynosi dokładnie . Oznacza to, że najczęściej występująca podsekwencja kończy się również na (tj. musi być podzielne przez ). Ale gdzie to bierze maksimum i ile to kosztuje ??? Dość kłopotliwe, ale nie mogłem tego pojąć ... ${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$ $t$ $k$ $t$

domotorp
źródło