Algorytmy kombinatoryczne w bioinformatyce − Zadanie III

Przed przystąpieniem do realizacji zadania proszę zapoznać się z wykładami 3 i 4.

Treść zadania:

Każda z osób konstruuje we własnym zakresie minimum 5 instancji, które następnie zostaną użyte w testach zaimplementowanego algorytmu. Instancje powstaną na bazie następujących plików zawierających przykładowe dane z sekwenatora 454: sample.fasta z sekwencjami nukleotydowymi oraz sample.qual z oceną jakości/wiarygodności każdego nukleotydu tych sekwencji. Każda z instancji składać się będzie z dwóch plików, jeden typu .fasta zawierający pięć losowo wybranych sekwencji nukleotydowych wraz z ich identyfikatorami, drugi typu .qual zawierający oceny wiarygodności odpowiadające wybranym sekwencjom, także z towarzyszącymi im identyfikatorami. Należy zwrócić uwagę na to, żeby sekwencje w obrębie jednej instancji nie miały długich powtarzających się fragmentów, co może się zdarzyć zwłaszcza gdy sekwencje położone są w pliku sample.fasta niedaleko siebie. Tak utworzone instancje należy zmodyfikować w celu uczynienia ich bardziej interesującymi z punktu widzenia poszukiwania w nich lokalnego dopasowania wielu sekwencji, tzn. należy zapewnić w nich obecność motywów (po jednym na instancję) o długości kilkunastu nukleotydów. W obrębie jednej instancji sekwencje powinny zawierać po jednym wystąpieniu motywu i nie wszystkie wystąpienia mają być identyczne (różnica pomiędzy dwoma wystąpieniami na 0-2 znakach). Motyw nie powinien być umieszczany na samym początku sekwencji. Edytując sekwencje proszę pamiętać, żeby długość ciągu liczbowego z ocenami wiarygodności była ostatecznie taka sama, jak długość odpowiedniej sekwencji nukleotydowej (pliki .qual także można edytować).

Należy zaimplementować algorytm heurystyczny o złożoności wielomianowej realizujący następujące czynności:
− wczytanie instancji;
− usunięcie z wczytanych sekwencji nukleotydowych pozycji o wiarygodności poniżej pewnego założonego progu (próg ten ma być parametrem ustawianym przez użytkownika); dla każdego pozostawionego znaku należy zapamiętać jego miejsce w sekwencji wejściowej (sprzed usunięcia znaków), gdzie numerację należy rozpocząć od 1;
− utworzenie grafu z wierzchołkami odpowiadającymi wszystkim kilkuliterowym podciągom sekwencji po powyższej operacji (długość podciągów z zakresu od 4 do 9 liter ma być drugim parametrem ustawianym przez użytkownika), każde wystąpienie takiego samego podciągu to osobny wierzchołek w grafie; dla każdego wierzchołka należy zapamiętać numer jego sekwencji wejściowej oraz pozycję wewnątrz tej sekwencji, będącą zapamiętanym wcześniej miejscem pierwszego znaku podciągu w sekwencji wejściowej;
− połączenie wierzchołków nieskierowanymi krawędziami, jeśli odpowiadają one takim samym podciągom występującym w różnych sekwencjach, a różnica w pozycjach podciągów wewnątrz sekwencji nie jest większa niż dziesięciokrotność długości podciągu;
− wyszukanie w grafie w sposób heurystyczny kliki lub struktury zbliżonej do kliki, w której każda sekwencja wejściowa będzie reprezentowana dokładnie jednym wierzchołkiem;
− wypisanie rezultatu na wyjściu w postaci: nr sekwencji wejściowej, nr pozycji w tej sekwencji, dla każdego podciągu wchodzącego w skład kliki (struktury zbliżonej do kliki) oraz sekwencję nukleotydową podciągu.

Klikę (strukturę zbliżoną do kliki) należy wyszukać algorytmem typowo grafowym, gdzie nie korzystamy z informacji o ciągach nukleotydowych. Może to być dowolna heurystyka wielomianowa (jej postać będzie miała wpływ na ocenę). Można skorzystać z algorytmu znanego z literatury, pod warunkiem powołania się na źródło i samodzielnej implementacji całości kodu. Najprostszym podejściem, które można zastosować, jest wyszukanie struktury typu gwiazda posiadającej po jednym wierzchołku z każdej sekwencji wejściowej.

Program należy przetestować na wygenerowanych instancjach z różnymi wartościami obu parametrów. Pożądanym efektem jest uzyskanie różnych wyników dla różnych ustawień, gdyż wartość progu wiarygodności może wyciąć inne znaki z sekwencji, a długość podciągów ma związek z rozlokowaniem różnic w poszczególnych wystąpieniach motywu, jak również może spowodować nieobecność krawędzi. W razie potrzeby proszę zmodyfikować instancje, zarówno pliki .qual, jak i .fasta, aby zaobserwować działanie programu w zmieniających się warunkach. Wskazane przez program podciągi są skróconą namiastką wystąpień motywów, w sekwencjach wejściowych odpowiadające im fragmenty będą się w ogólności różniły, można je porównać z motywem wprowadzonym do instancji.

W sprawozdaniu należy zamieścić: opis algorytmu ze szczególnym uwzględnieniem wyszukiwania kliki, oszacowanie złożoności algorytmu, trzy wybrane instancje dające najbardziej interesujące wyniki z zaznaczonymi fragmentami odpowiadającymi wprowadzonemu motywowi (w obu plikach: .fasta i .qual), wyniki testów przeprowadzonych na tych trzech instancjach z różnymi zestawami wartości parametrów (po trzy testy na instancję, w wynikach proszę już nie powielać całych instancji), wnioski.

Termin realizacji:

Omówienie zadania: 4 listopada (grupa wtorkowa) i 30 października (grupy czwartkowe).
Oddanie sprawozdania i zaliczenie zadania: 16 grudnia (grupa wtorkowa) i 11 grudnia (grupy czwartkowe).