Detta är hemsidan för en gammal kursomgång. För aktuell information gå till hemsidan för aktuell kursomgång.

Labb L4: CLP för DNA-sekvensning

Viktigt!
CSC:s hederskodex tillämpas i kursen.

Det här är en betygshöjande laboration utan bonuspoäng och tidsfrist.

I denna betygshöjande laboration prövar ni att skriva ett Prolog-program som använder Constraint Logic Programming för att hitta den billigaste kombinationen av primers nödvändiga för att sekvensera ett antal gener i flera organismer.

Bakgrund

När man studerar gener måste man i många fall välja ut en kort region (ca 20 nukleotider) både före och efter genen som fungerar som start- och stopp-block. En sådan region kallas för primer. Man kan inte välja vilka primers som helst. Dels ska de vara lämpliga rent molekylärt, dels ska de vara unika för genen så att man vet vad man sekvenserar.

För de som arbetar med många gener blir det naturligtvis många primers och eftersom dessa kostar pengar kan de stå för en ansenlig del av den totala experimentkostnaden. Anders Andersson var doktorand på Bioteknik när han insåg att han skulle kunna spara hundratusentals kronor genom att välja ut sina primers smart. Han tittade nämligen på gener från två arter samtidigt vilket gjorde att han kunde använda samma primer i båda arterna.

Vi ska betrakta en förenklad och generaliserad version av Anders problem och formulera en lösning med hjälp av CLP.

Figur 1: Primers för två genomsekvenser. Ett enkelt primer problem. Två arter har vardera tre gener (1A/1B, 2A/2B, och 3A/3B) och varje gen har två till tre möjliga primers. En slösaktig lösning använder en primer per gen. Man kan halvera experimentkostnaden genom att välja primers 2, 3, och 6 och ändå läsa av alla sex generna. Om man nödvändigtvis vill använda primer 1 måste man däremot använda fyra primers.

Data

Primers representeras av heltal i intervallet [1,n]. Indata består av en lista med gener och vilka primers som de kan använda. Vi struntar helt i vilken art en gen tillhör genom att anta att ingen primer används till olika gener i samma art.

Listan med gener och deras möjliga primers består av termer på formen pri(gen, primers), där gen är en atom och primers är en lista med heltal. Du kan utgå ifrån att varje gen har minst en primer. Om två gener råkar dela en primer i indata betraktar vi det som att de är i olika arter.

I filen /info/progp12/prolog/primerexamples.pl finns tolv uppsättningar testdata av olika storlek att jobba med. Deras egenskaper listas i tabell 1 nedan.

Uppgift

Skriv ett predikat choose_primer/3 som tar som argument antalet primers och listan med gener, och unifierar det tredje argumentet med ett förslag på vilka primers som ska användas.

Dataset	Antal gener per art	Antal arter	Max primers per gen	Antal primers	Bästa lösning
ex1	3	1	2	6	3
ex2	3	22	2	6	3
ex3	3	2	2	6	3
ex4	3	3	2	9	4
ex5	3	5	2	9	4
ex6	3	3	2	7	5
ex7	2	4	5	15	3
ex8	10	2	5	43	16
ex9	20	2	3	54	28
ex10	50	2	3	133	74?
ex11	100	2	3	291	157?
ex12	100	3	3	330	182

Tabell 1: Egenskaper hos testdata. De sex första exemplen är konstruerade manuellt, och resten är framslumpade data. Kolumnen "antal primers" anger hur
många primers som finns i datasetet. Den sista kolumnen talar om hur många primers som räcker till alla gener. Ett frågetecken anger att det är den bästa
lösning som mitt exempelprogram hittade inom en minut.

För varje gen ska en primer väljas ut.

Problemet måste formuleras som ett villkorsprogram (med domänvariabler och bivillkor på dessa) och din lösning ska använda CLP-biblioteket i Sicstus Prolog (eller annan valfri Prolog) för att räkna fram en lösning som använder så få primers som möjligt. Det är ett krav att din lösning återanvänder primers! Utdata ska ange hur många och vilka primers som används.

Lite ledning

I CLP-manualen och andra källor ges exempel i form av instanser av problem. Lösningar ges genom att formulera termer av domänvariabler som ställs upp med diverse bivillkor och dessa domänvariabler har sedan en direkt tolkning i problemlydelsen. I den här labuppgiften formuleras däremot ett generellt problem och ditt program ska läsa in godtyckliga instanser och generera en lösning för dessa. Det innebär att domänvariablerna måste skapas dynamiskt. Men det är lätt! Antag att vi vill skapa $n$ variabler över domänen {0, 1}:

gen_var(0, []).
gen_var(N, [X|Xs]) :-
        N > 0,
        M is N-1,
        gen_var(M, Xs),
        fd_domain_bool(X). % The domain of X is constrained to 0/1

Första argumentet till gen_var anger hur många domänvariabler som ska skapas och andra argumentet unifieras till listan med variabler. Dessa kan man sedan skapa villkor för.

| ?- gen_var(3, L), sum(L, #=, 3).
L = [1,1,1] ?
yes
| ?- gen_var(3, L), sum(L, #=, 2).
L = [_A,_B,_C],
_C in 0..1,
_B in 0..1,
_A in 0..1 ?
yes

Ansats

Det finns många sätt att betrakta detta problem, men en tänkbar ansats ges här som ledning.

En indikatorvariabel är en binär variabel som används för att signalera användande eller status. De används gärna i sannolikhetsberäkningar, men är också praktiska att använda i kombinatoriska argument. Definiera indikatorerna I_1, ..., I_n så att I_i=1 om primer i används och =0 annars.

På samma sätt ska J_g,i indikera om genen g använder primer i eller inte. Dessa två indikatorer kan nu koda två villkor som måste ställas. Först kräver vi att varje gen har en primer: Σ_iJ_g,i=1. Summan är tagen över de primers som är tillåtna för gen g.

Det andra villkoret knyter ihop de två uppsättningar av indikatorer: ∀g, i: I_i≥J_g,i.På detta sätt försäkrar man sig om att en gen inte "tror" att den kan använda primer i utan att just den är vald.

Om CLP i Sicstus

Ni ska använda CLP-biblioteket för ändliga domäner, clpfd. Jag föreslår att ni startar er kod med predikatet :- use_module(library(clpfd)). som alltså saknar huvud. Läs i Sicstus dokumentation om vilka predikat som finns! Från kursen lab- webbsida finns en PDF med dokumentationen länkad. Den finns även online på http://www.sics.se/sicstus/docs/latest4/html/sicstus.html. Det finns många användbara predikat i biblioteket. Avsnitt 34.9, om att skriva egna primitiva CLP-villkor, ska ni hoppa över helt. Predikaten sum och labeling kan vara användbara, särskilt som det senare kan minimera en variabel. Läs särskilt på om "flaggorna" till labeling:

Med minimize(X) instruerar man CLP-lösaren att hitta ett minimalt värde på X .
Med time out begränsar man söktiden och den bästa lösningen fram till att tiden tar slut returneras.
Den automatiskt valda CLP-lösaren i labeling är ineffektiv. Prova några alternativ. Vilken är bäst?

Redovisning

Skicka ett ebrev till kursledaren med ditt/ert lösningsförslag dvs programkod (naturligtvis strukturerad, dokumenterad och lättläslig) samt testkörningar du/ni gjort. Ange ditt/era namn och epostadresser. Kursledaren återkommer med redovisningstid.