Author: bartek

ONA 13 – Metody Monte Carlo i rozwiązania równań nieliniowych

Dziś przede wszystkim zajmowaliśmy się zerami funkcji nieliniowych, ale zrobiliśmy też dygresję (w zasadzie uzupełnienie do wykładu o całkowaniu numerycznym) n.t. metod Monte Carlo. Notatki do równań nieliniowych znajdą Państwo tu. Opis całkowania metodą MC znajdą Państwo np. tu

Zadania na dziś:

1. Napisz program, który znajduje  przybliżenie liczby Pi przy pomocy równania x**2+y**2<=1

2. Napisz program, który korzysta z metody bisekcji i oblicza wartość pierwiastka kwadratowego z 2. Jakiego równania zera szukamy? ile iteracji potrzeba?

3. Napisz program, który korzysta z metody stycznych, aby obliczyć tę samą wartość. O ile szybciej możemy znaleźć dokładną wartość?

4 (*). Zaimplementuj metodę iteracji prostej Banacha dla rozwiązania równania Keplera.  Możesz posiłkować się tym artykułem

WBO 12 – Mapowanie odczytów NGS

Dziś mamy zajęcia o mapowaniu odczytów. Wykład tutaj: wyk12-ngs

Zadania na dziś dotyczą głównie indeksów sekwencji:

1. Napisz funkcję compute BWT(txt), która oblicza BWT (w postaci napisu) dla zadanej sekwencji DNA oraz tablice C(x) i OCC(i,x)

2. Wylicz te wartośći dla sekwencji:
CGAGCCGCTTTCCATATCTATTAACGCATAAAAAACTCTGCTGGCATTCACAAATGCGCAGGGGTAAAACGTTTCCTGTAGCACCGTGAGTTATACTTTGT

3. Korzystając z metody podanej na wykładzie wyszukaj wystąpień napisu AAAC w podanej sekwencji

4. Korzystając z podanej metody omijania błędów znajdź sekwencję (z co najwyżej jednym błędem) AAAACTCCGCTGGCATTCACAAAT

Zadanie domowe: Użyj stworzonego dziś kodu aby wyszukać wszystkich promotorów z pliku ecoli_proms.fa w sekwencji genomu E. coli Escherichia_coli_str_k_12_substr_mg1655.ASM584v2.dna.chromosome.Chromosome.fa

WBO – Zadanie 2

Naszym zadaniem będzie analiza ewolucji białek z rodziny Homeodomain (HOX). W szczególności interesować nas będą białka pobrane z bazy homeoDB dla 4 gatunków: Człowieka, myszy, muszki owocowej i chrząszcza: homeo2.fa. Co istotne, w pliku Fa opis genu obejmuje: Gatunek|Nazwę genu|rodzinę genu|klasę genu

Podzielimy to zadanie na kilka podzadań:

  1. Korzystając z lokalnej instalacji narzędzia BLAST stwórz bazę danych sekwencji z pliku Fasta i następnie wylicz przybliżoną macierz podobieństwa poprzez wykorzystanie funkcji oceny BLAST. Dla genów niepodobnych wg blast, przyjmij ustaloną niską wartość podobieństwa. (3 pkt)
  2. Korzystając z metody Neighbor joining skonstruuj drzewo genów dla tej rodziny.  (2 pkt)
  3. Zakładając, że człowiek z myszą i muszka z chrząszczem są najbliżej spokrewnionymi gatunkami spośród 4 danych dokonaj uzgodnienia otrzymanego drzewa genów z drzewem gatunków, tj. znajdź optymalny (w sensie duplikacji i strat) scenariusz ewolucyjny dla drzewa gatunków i Twojego  drzewa genów.   Czy możesz wybrać taki scenariusz optymalny, który jest zgodny z opisem genów w oryginalnym pliku (zakładamy, że geny z  różnych rodzin w tym samym gatunku to na pewno paralogi, a geny o tej samej nazwie u różnych gatunków to ortologi). (7 pkt)
  4. Wykorzystując narzędzie Hmmer dokonaj opisu domen białkowych dla klas genów hox (białka o tej samej ostatniej kolumnie w pliku fasta). Sprawdź, jak często białka należące do każdej z klas zawierają domeny należące do innej klasy. (4 pkt)
  5. Opisz swoje rozwiązanie (1 strona) i wyniki (max 2 strony) w krótkim raporcie w .pdf (4 pkty)

Wynik w postaci programu w pythonie i raportu w pdf wyślij na adres e-mail wykładowcy z dopiskiem [WBO-2-2018] do 22. czerwca 2018.

WBO 11 – Motywy sekwencyjne i ich wyszukiwanie

Dziś rozmawialiśmy o reprezentacji i wyszukiwaniu motywów sekwencyjnych: wyk11-motifs

Zadania na dziś:

1. Pobierz listę promotorów e_coli w pliku fasta: ecoli_proms.fa

2. Zapoznaj się z modelem macierzy motywów z modułu Bio.motifs i jego dokumentacją 

3. Zaimplementuj prostą, zachłanną metodę consensus dla wyszukiwania motywów, zastosuj ją do promotorów e.coli i obejrzyj wyniki dla motywów długości 3,4,5,6. Schemat algorytmu jest następujący:

  • zaczynając od dowolnego miejsca w pierwszej sekwencji skonstruuj na jego podstawie model PWM
  • dla każdej kolejnej sekwencji wybieraj sekwencję najlepiej pasującą do obecnego modelu PWM
  • Po wybraniu sekwencji skonstuuj nowy model PWM, wzbogacony o tę sekwencję
  • Po wykonaniu tej procedury dla wszystkich punktów startowych z sekwencji 1. zwróć kilka (np. 5) najlepszych macierzy

Powtórz tę procedurę dla kilku różnych permutacji pliku wejściowego.

4. Porównaj wyniki ze znanymi motywami promotorowymi w E. coli

5. Wykonaj analizę tych samych promotorów przy pomocy MEME i porównaj wyniki z otrzymanymi z consensusa

ONA 12 – Obliczenia symboliczne i pakiety do obliczeń

Dzisiejszy wykład porównujący cechy różnych pakietów do obliczeń jest tu: ONA12-Pakiety-oprogramowania

Zadania na dziś są dość proste i dotyczą przede wszystkim obliczeń symbolicznych i pakietu sympy (można to robić w platformie jupyter)

  1. Przy użyciu pakietu sympy, zbadaj podstawowe możliwości obliczeń symbolicznych: stwórz zmienną sumboliczną x (Symbol(‘x’)), stwórz wyrażenie wielomianowe (np. x**2-2) oraz wyrażenie trygonometryczne (np. sin(x)) i policz dla nich pochodne, całki (oznaczone i nieoznaczone) oraz granice (w 0, z prawej i lewej strony oraz , granice 1/x w nieskonczonosci: sympy.oo,).
  2. Zobacz jak wyniki tego typu zadań wyglądają w Wolfram Alpha
  3. Zarejestruj się w systemie SageMath i tam spróbuj rozwiązać te same problemy
  4. (*) Spróbuj rozwiązać symbolicznie układ równań różniczkowych zwyczajnych z poprzednich zajęć (model Lotki-Volterry albo Zombie Invasion) w jednym z wymienionych wcześniej pakietów

Tymczasem, za tydzień, na wykładzie mamy kolokwium. Zagadnienia do powtórki są tutaj: ONA_powtorka

Przykładowe kolokwium jest tu: kolokwium-2017 ( w tym roku dodatkowe są zagadnienia z kompresji).

Dodatkowe konsultacje przed kolokwium zrobimy w czwartek o 10:15 w sali 2041 (lab)

Egzamin będzie w poniedziałek 25. VI o godzinie 10tej.

Egzamin poprawkowy, 14. IX, też o 10tej

WBO 10 – Uzgadnianie drzew

Dzisiaj na wykładzie zajmowaliśmy się uzgadnianiem drzew.

Slajdy do wykładu:

Zadania na lab:

Dzisiaj zajmiemy się uzgadnianiem drzew. Rozważmy sytuację, gdy mamy 1 drzewo gatunków S i drzewo genów G zgodne z tym drzewem gatunków (dla każdego genu g\in G , s(g)\in S). Na początek możesz

1. Napisz algorytm LCA(G,S), który znajduje mapowanie LCA i zwraca je w postaci słownika

2. Napisz funkcje liczące koszty DC(G,S), D(G,S) a następnie wykorzystaj wzór ze slajdu 10, który wylicza koszt L(G,S)

3. Napisz funkcję fat_tree(G,S), która tworzy scenariusz uzgadniający G i S (nie zawsze optymalny), gdzie w korzeniu występują wszystkie duplikacje, zaś wszystkie straty występują w krawędziach prowadzących do liści. Scenariusz w naszym przypadku, to etykietowanie drzewa gatunków zdarzeniami ewolucyjnymi, D i L. Zauważmy, że zarówno straty jak i duplikacje występują na krawędziach drzewa gatunków.

4. Napisz funkcję optimal_tree(G,S), która znajduje jeden z optymalnych scenariuszy uzgadniających G i S. W tym celu musimy przenieść w drzewie “grubym” duplikacje w dół, a straty w górę, jeśli to możliwe.

5. sprawdź na przykładzie drzewa z wykładu (abcde), czy Twój algorytm działa poprawnie

ONA – Zadanie 3 – kompresja

Naszym zadaniem będzie napisanie programu, który będzie wykonywał kompresję i testował jej zachowanie dla różnych dugości pliku i parametrów kompresji. Kolejne elementy podzadania to:

1) Zaimplementuj prosty algorytm kompresji oparty o metodę Lempela i Ziva (LZ77) omawianą na wykładzie. Powinna to być funkcja w pythonie lz77_compress(napis, rozmiar_słownika ), która pobiera napis w argumencie, a następnie zwraca jego wersję skompresowaną w postaci napisu. Zaimplementuj także funkcję odwrotną lz77_decompress(napis)>  (5 punktów)

2) Napisz dwie funkcje generujące napisy o zadanej długości. gen_losowy(dlugosc, zestaw_znakow), ktora generuje losowy ciąg znaków pochodzących z zadanego zestawu znaków. Zarówno zestaw dozwolonych znaków, jak i wynik jest w formie napisu. Drugi z generatorów powinien być mniej losowy. Najlepiej, gdyby losował kolejne znaki, ale za każdym razem wstawiał ciąg po 100 identycznych znaków. (5 punktów)

3) Napisz funkcję testuj(kompresor,generator, lista_długości), która używa podanego generatora do wygenerowania zestawu napisów o długościach zadanych w parametrze lista_dlugosci. Następnie używa podanego w pierwszym argumencie kompresora, aby dokonać kompresji wszystkich tych napisów. Ostatecznie, funkcja zwracałaby listę długości wszystkich skopmpresowanych napisów. (5 punktów)

4) Użyj napisanych funkcji, oraz swojej wiedzy o aproksymacji funkcji do tego aby napisać program pozwalający  znaleźć funkcje opisujące:

  • zależność rozmiaru skompresowanego od wejściowego jako funkcji liniowej lub kwadratowej dla obu generatorów
  • zależność współczynnika kompresji (wyestymowanego w poprzednim punkcie) od rozmiaru słownika

Obraną metodę i wyniki opisz nie tylko w komentarzach w pliku źródłowym, ale także w postaci krótkiego raportu (maksymalnie 2 strony), ilustrowanego sensowymi wykresami (10 pktów)

Rozwiązania ( w postaci 1 pliku .py i 1 pliku .pdf) przesyłamy do 3. czerwca, e-mailem do wykładowcy, proszę pamiętać o dopisku [ONA-2018-3] i o umieszczeniu plików jako standardowych załączników.

ONA 11 – Różniczkowanie i całkowanie numeryczne

Dziś będziemy zajmować się różniczkowaniem i całkowaniem numerycznym. Slajdy są tu: ONA11-calkowanie

Przydatny będzie nam przede wszystkim pakiet scipy.integrate ale będziemy też korzystać z nowych funkcji pakietu matplotlib, takich jak wykresy strzałkowe

0. Na początek proponuje obejrzeć sobie program opisujący model Lotki-Volterry ( lotka_volterra ) i spróbować wykonać go po kawałku ze zrozumieniem. Jeśli są pytania, to proszę pytać

1. Naszym właściwym zadaniem jest budowa podobnego modelu dla problemu inwazji Zombie (opisanego w artykule naukowym , kopia lokalna tu: Zombies). Mamy tu 3 zmienne: ludzi niezarażonych (S), zombie (Z) oraz ofiary konfliktu (R). System jest dynamiczny, a jego zmiany opisują równania różniczkowe:

  • dS/dt = P – B*S*Z -D*S,
  • dZ/dt = B*S*Z +G*R – A*S*Z,
  • dR/dt = D*S + A*S*Z – G*R,

gdzie

  • P oznacza przyrost naturalny ludzi,
  • B – współczynnik z którym zombie spotykając niezarażonego może go zarazić,
  • D – współczynnik śmiertelności ludzi z przyczyn naturalnych,
  • G – prawdopodobieństwo, że zombie powstanie z martwej ofiary,
  • A – szansa na to, że w pojedynku człowieka z zombie, to zombie zostanie pokonane

Interesują nas następujące pytania:

a) Jak wygląda ewolucja systemu w czasie (w zakresie 0..5000),  jeśli na początku jest tylko 1000 ludzi niezarażonych (nie ma zombie, ani ciał) i mamy następujące prametry:

  • P=0.0001
  • D=0.0001
  • B=0.0095
  • G=0.0001
  • A=0.0001

Rozwiązanie przedstaw na wykresie 3 zmiennych (S,Z i R) od czasu

b) Czy zagładę populacji można zatrzymać poprzez zwiększanie współczynnika urodzin P? Rozwiązanie uzasadnij. Który ze współczynników musiałby wynosić 0, żeby populacja mogła poradzić sobie z zombie?

c) Zaprezentuj pole wektorowe populacji zombie i ludzi względem parametrów A i B?

d*) Zaprezentuj pole wektorowe 3d dla zmiennych S,Z,R