O pewnych algorytmicznych problemach tekstowych

Tomek Waleń opowie o wspólnej pracy z P. Kolmanem. Podczas seminarium zostanie przybliżony problem porównywania sekwencji genomów. W szczególności problem obliczania odległości pomiędzy napisami liczonej w liczbie odwróceń (całych bloków), potrzebnych do przekształcenia jednego napisu w drugi (reversal distance). Przedstawiony zostanie algorytm O(k) aproksymacyjny dla problemu obliczenia odległości pomiędzy dwoma k-napisami (tzn. napisami, w których każdy znak alfabetu występuje co najwyżej k razy). Poprzedni znany algorytm ma współczynnik aproksymacji O(k^2). Marcin Kubica opowie o problemie uliniowienia wielu sekwencji (niekodującego) RNA. Problem ten jest modelowany za pomocą grafów liniowych -- sekwencjom RNA odpowiadają grafy liniowe, a problemowi uliniowienia odpowiada maksymalny zagnieżdżony podgraf liniowy (MAX-NLS). Dla ogólnych grafów liniowych problem ten jest NP-zupełny. Dotychczas znana aproksymacja tego problemu charakteryzuje się współczynnikiem O(\log^2 n) i działa w czasie O(kn^5). Przedstawimy ulepszoną wersję tej aproksymacji -- działającą w czasie O(kn^2) oraz pokażemy, że współczynnik aproksymacji jest rzędu O(\log n). Dla grafów liniowych generowanych przez sekwencje RNA pokażemy 1/4-aproksymację działającą w czasie O(kn).