WBO 1 – O sekwencjach DNA i grafach

Dzisiaj będziemy rozmawiać o sekwencjach DNA i grafach. Slajdy do wykładu są tu: wyk1

English version below

Zasadniczo pracujemy w języku python. Jeśli ktoś ma kłopoty z interpreterem w labie, to może korzystać z serwera jupyter, używając hasła: 2020-studenci

W laboratorium spróbujemy zająć się następującymi kwestiami:

1. Spróbujemy wczytać zestaw sekwencji z pliku FASTA przy pomocy biblioteki Bio.Seq z pakietu Biopython. Mamy do dyspozycji plik test_fasta Na początek warto go wczytać i wypisać do innego pliku zestaw sekwencji komplementarnych do sekwencji wejściowych.

2. Napiszemy funkcje kmers(s,k), która na podstawie sekwencji DNA daje nam wszystkie k-mery (podsekwencje długości k) składające się na widmo sekwencji s. Rozważymy dwa warianty – gdy widmo zawiera tylko podsekwencje s, i drugą, gdzie do widma zaliczamy też fragmenty sekwencji komplementarnej.

3. Napiszemy funkcje euler(kmers) i hamilton(kmers), które tworzą graf na podstawie widma k-merów i znajdują w nim wszystkie ścieżki (może być naiwna, jeśli chodzi o złożoność)

4. Spróbujemy rozwiązać problem znajdowania zestawu sond komplementarnych z ostatniego slajdu.

Praca domowa (2 pkt):

Napisz program, który znajduje minimalne k, dla którego istnieje zbiór sond długości k komplementarnych do zestawu sekwencji (każda sonda komplementarna do dokładnie jednej sekwencji z zestawu) zadanego w pliku .fasta. Rozwiązanie polega na przysłaniu programu (z komentarzami), który znajduje minimalne k oraz wyniku jego uruchomienia dla wybranych genów drożdży Saccharomyces cerevisiae yeast.fa.

Prace domowe trzeba przysłać na mój adres e-mail (z dopiskiem [WBO] w tytule) przed następnymi zajęciami w laboratorium.

4*. Zastanów się nad problemem zestawu sond komplementarnych, gdzie zamiast równej długości wszystkich sond założymy, że powinny mieć tę samą temperaturę topnienia.

In general we are working in python. If you have trouble with the lab computers, please use our jupyter server, with the secret: 2020-studenci

Today’s topics:

1. We will read a FASTA file using the  Bio.Seq library from Biopython package. We can use the file test_fastafor testing. Just to start things off, you can try to read all sequence records from it and save their reverse complements to another file.

2. Let’s write a function kmers(s,k), that returns all k-mers (a k-mer spectrum) for a given DNA sequence s and k-mer length k. You can consider two variants – one, where we only consider substrings of s, and another, where sequence spectrum also contains reverse complementary sequences.

3. Write functions euler(kmers) and hamilton(kmers) that create a graph representation of a k-mer set, according to hamiltonian or eulerian approach. The functions should return a sequence of k-mers that form a hamiltonian or eularian path corresponing to a solution – a string. The functions do not have to be very efficient.

4. Try to solve the problem of finding a set of probes f lengtgh k representing a set of input sequences. Test it on the test_fasta file.

Homework (2 pts):

Write a program that finds a minimum k, for which there exist a solution to the last problem for a given set of sequences in a fasta file. Your solution is counted if you send a program and the result (k) of running it on the set of yeast gene sequences in this fileyeast.fa.

Send your homeworks by e-mail to me(with [WBO] in the subject) before out next lab.

4*. You can also consider (as a brain teaser) how would you approach the probe design problem for a given set of sequences assuming you need to find sequences with equal melting temperature.