Metody Bioinformatyki - Projekt

Podstawowe informacje

Formalne informacje o projekcie (terminy, zasady zaliczania, skład osobowy, itp.) można znaleźć tutaj: MBI - projekt
Ze swojej strony zwracam uwagę na terminy i kary związane z opóźnieniami.

Nie jest narzucony konkretny język programowania ani środowisko (z wyjątkiem zalecenia w przypadku grupy projektów nr 1).
Przy realizacji projektów można korzystać z zewnętrznych bibliotek i narzędzi, jednak należy mieć na uwadze, że nie wolno używać oprogramowania nielegalnego, ani gotowych rozwiązań.

Uwaga: limit przydzielonych mi studentów został wyczerpany, tj. mam 14/14 osób zapisanych na projekty, więc proszę zapisywać się do innych prowadzących projekty.

Lista projektów 2014L

• Grupa projektów 1: Program demonstracyjny
  

  Napisać aplikację, która pozwala zrozumieć działanie wskazanego algorytmu. Pożądane jest, aby aplikacja mogła być uruchamiana przez przeglądarkę (być może zaimplementowana w JavaScript + HTML5 + CSS3). Użytkownik może wprowadzić własne dane i śledzić (krok po kroku) sposób wykonywania obliczeń. Wybierając to zadanie proszę wskazać algorytm, który będzie obrazowany. Przykłady algorytmów:

  1. badania podobieństwa dwóch sekwencji, Needlemana-Wuncha z afiniczną funkcją kary za przerwę Zajęty Zespół: Svitlana Buruk i Adam Tkaczyk
  2. badanie podobieństwa dwóch sekwencji, Smitha-Watermana z afiniczną funkcją kary za przerwę Wolny
  3. badania podobieństwa dwóch sekwencji o liniowym koszcie pamięciowym, Myers-Miller Wolny
  4. obliczania macierzy podobieństwa metodą BLOSUM Wolny
  5. wyszukiwania sekwencji podobnej do danej metodą BLAST Zajęty Zespół: Sylwia Kamińska i Michał Ciechański
  6. wyszukiwania sekwencji podobnej do danej metodą FASTA Wolny
  7. badania podobieństwa trzech sekwencji, metodą programowania dynamicznego, z liniową funkcją kary za przerwę Wolny
  8. badania podobieństwa trzech lub więcej sekwencji metodą progresywną Wolny
  9. wyszukiwania motywów dla zbioru sekwencji metodą wyszukiwania mediany Wolny
  10. generowania profili genetycznych dla danej mieszaniny i określonej liczby osób Wolny
  11. generowania profili genetycznych dla danego zbioru haplotypów Wolny
  12. obliczania najbardziej prawdopodobnych haplotypów dla danej grupy profili genetycznych Wolny
  13. rozwiązywanie problemu częściowego strawienia Wolny
  14. obliczanie sekwencji na podstawie odczytów metodą grafu pokrycia Wolny
  15. obliczanie sekwencji na podstawie odczytów metodą grafu de Bruijna Wolny
  16. dekodowania Viterbiego, oblicza ciąg stanów dla ukrytego modelu Markova Wolny
  17. dekodowania Bauma-Welcha, oblicza ciąg stanów dla ukrytego modelu Markova Wolny
  18. obliczanie prawdopodobieństwa ciągu obserwacji dla ukrytego modelu Markova metodą prefiksową Wolny
  19. obliczanie prawdopodobieństwa ciągu obserwacji dla ukrytego modelu Markova metodą sufiksową Wolny
  20. redukcja wymiarów za pomocą metody PCA Wolny
  21. grupowanie metodą najbliższych sąsiadów Wolny
  22. grupowanie hierarchiczne Wolny
  23. obliczanie struktury drugorzędowej metodą Nussinov Wolny
  24. obliczanie struktury drugorzędowej metodą Zukera Wolny
  25. inny algorytm (należy podać jaki) Wolny

• Projekt 2: assembler DNA, graf de Bruijna
  Status: Wolny

  Aplikacja prostego assemblera DNA, dostarcza wynikowego napisu na podstawie krótkich pod-napisów o danej długości, które się nakładają. Wykorzystać algorytm grafu de Bruijna (patrz wykład o sekwencjonowaniu DNA).

• Projekt 3: assembler DNA, sparowane końce
  Status: Wolny

  Aplikacja do ustalania kolejności kontigów i tworzenia scafoldów. Dla danego zbioru kontigów oraz sekwencji PET (patrz wykład o sekwencjonowaniu) obliczyć kolejność kontigów. Algorytm może być zachłanny, tzn. badać wszystkie permutacje, chociaż zachęcam do próby użycia własnej heurystyki.

• Projekt 4: Implementacja algorytmu badającego podobieństwo trzech sekwencji
  Status: Zajęty Zespół: Artur Kaczmarczyk i Monika Grzechnik

  Aplikacja wykorzystuje programowanie dynamiczne (macierzy trójwymiarowa) i oblicza najlepsze dopasowanie dla trzech podanych sekwencji (opis algorytmu - wykład dotyczący podobieństw wielu sekwencji).

• Projekt 5: Implementacja algorytmu Nussinov do obliczania struktury drugorzędowej DNA i RNA
  Status: Zajęty Zespół: Jerzy Balcerzak i Oleg Druzhynets

  Aplikacja oblicza strukturę drugorzędową cząsteczki DNA lub RNA wykorzystując algorytm Nussinov (opis algorytmu - wykład o strukturach drugorzędowych RNA)

• Projekt 6: Implementacja algorytmu BLOSUM do obliczania macierzy substytucji
  Status: Zajęty Zespół: Opasiak Krzysztof, Kubik Marcin i Sosnowski Jacek

  Dla podanej grupy sekwencji obliczyć macierz BLOSUM. Sekwencje powinny być tej samej długości. W wyniku działania programu dostarczana będzie macierz podobieństw (zawierająca logarytmy), macierz podstawień (zlicza wszystkie pary danych symboli) oraz częstości poszczególnych symboli. Wykorzystać algorytm omawiany na wykładzie dotyczący macierzy substytucji.

• Projekt 7: Automatyczne odtwarzanie sekwencji DNA kodującej białko za pomocą ukrytych Modeli Markowa
  Status: Zajęty Zespół: Konrad Piekutowski, Karol Szczapa i Szymon Szepietowski

  Dla danej sekwencji DNA jednoznacznie (zgodnie z tablicą kodów genetycznych) można uzyskać sekwencje RNA i sekwencję białka, którą jest zakodowane; każdy kodon (trójka nukleotydów) jednoznacznie określa aminokwas. Nie można jednoznacznie odtworzyć sekwencji RNA i DNA mając sekwencję białka (ciąg aminokwasów), ponieważ dany aminokwas może być kodowany przez więcej niż jeden kodon (kodonów jest 64, zaś aminokwasów 20). Można tutaj się posłużyć tabelami częstości kodonów dla danego organizmu. Wykorzystanie ukrytego modelu Markowa pozwoli na odtworzenie struktury DNA i RNA bez potrzeby tego rodzaju parametrów. Wykorzystać algorytm Viterbiego oraz trenowania Viterbiego omówione na wykładzie dotyczącym Modeli Markowa.

• Projekt 8: Własny
  Status: Wolny

  Istnieje możliwość zaproponowania i realizacji własnego projektu, do czego, gorąco, zachęcam. Tematyka projektu powinna wiązać się z tematyką wykładu. Złożoność projektu powinna być porównywalna do tematów w obecnej liście.