Nie jesteś zalogowany |
O pewnych algorytmicznych problemach tekstowych
- Prelegent(ci)
- Marcin Kubica i Tomasz Waleń
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 9 marca 2006 12:15
- Pokój
- p. 5870
- Seminarium
- Seminarium "Algorytmika"
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).
