Generator instancji:

parametry wejściowe: 
* n - długość DNA,  (zakres badań 300-700bp)
* k - długość oligo, (7-10)
* delta_k - plus minus ile zmienia się długość, (0 - 2)
* l_neg - liczba błędów negatywnych, (0 lub min. 10 BŁĘDÓW (ale nie więcej niż 10-15 PROCENT!))
* l_poz - liczba błędów pozytywnych,  (0 lub min. 10 BŁĘDÓW (może być więcej niż 10 PROCENT))
* repAllowed - czy dopuszczalne powtórzenia (nieistotne, jeżeli l_neg > 0),
* probablePositive - 1 (tak), 0 (nie) - czy błędy pozytywne są sensownie generowane


Program:

Ma mieć menu główne:

1. Generator instancji
2. Algorytm naiwny
3. Metaheurystyka

Pierwsza pozycja w nim to Generator Instancji. Jego podmenu:

1. Wczytaj DNA z pliku
2. Generuj ręcznie.

Druga opcja wyświetla ciąg pytań o parametry opisane na początku pliku. Po ich podaniu ma się wyświetlić wygenerowane DNA, liczba elementów spektrum i w ogóle info o nim. Po tym ma być pytanie, czy zapisać instancję do pliku (format tekstowy, ale dowolny, byle wasz program umiał to czytać potem). Uwaga: te pytania o parametry mogą być męczące, więc program ma rejestrować wciśnięcie enter po każdym pytaniu i wtedy przyjmować wartości domyślne:
n = 400
k = 8
delta_k = 2
l_neg = 0
l_poz = 0
repAllowed = true
probablePositive = 0

Czyli jeżeli program najpierw zapyta jakie ma być 'n', a my po prostu wciśniemy enter, to przyjmie 400. Potem pyta o 'k', potem o 'delta_k' i tak do końca.
probablePositive - jeżeli jest ustawione na 0 (nie), to błedy pozytywne to po prostu losowo wygenerowane sekwencje o długości k +/- delta_k. Jeżeli probablePositive = 1, to wtedy działa to inaczej. Algorytm bierze jakiś element ze spektrum, np. AGTCGTCG, kopiuje go dwa razy (jako 2 błędy pozytywne, zakładamy, że ich liczba będzie parzysta) i w tej kopii zmienia ostatni nukleotyd oraz (osobno) środkowy, np. końcowy na A, C lub T w przykładzie dla AGTCGTCG i powiedzmy że powstał AGTCGTCA jako pozytywny błąd. Oraz druga kopia, bierzemy oryginalny AGTcgTCG i zmieniamy w nim albo środkowe C albo G na jakąś inną literę. Czyli pozytywne błędy to oligonukleotydy bardzo podobne do tych prawdziwych, ale z losowo dobranym ostatnim lub środowym nukleotydem.


delta_k - zakres od 0 do 2, wpisuje użytkownik czyli my. Jeśli wpiszemy zero, to wszystko co tu wyjaśnię poniżej nie ma sensu i długość każdego oligonukleotydu w spektrum to dokładnie k. Załóżmy jednak, że wpisano w generatorze delta_k = 2 (maks. wartość). Wtedy powstawanie spektrum wygląda tak: Pierwszy oligo wędruje do spektrum niezmieniony, on zawsze ma mieć długość k (delta nieważna). Następnie przesuwamy się "oknem" o długości k po wygenerowanym łańcuchu DNA o długości n  O JEDNĄ LITERĄ W PRAWO. Zawsze, co by się nie działo i jakie by nie było delta_k, przesuwamy to okienko o jedną pozycję w prawo. No to jak już przesunęliśmy okienko wycinania substringiem k liter o jedną pozycję, program robi dwie rzeczy (przypominam, zakładamy, że w generatorze wcześniej wpisaliśmy, że delta_k = 2). Najpierw program losuje liczbę z przedziału od 0 do delta_k, czyli albo wylosuje 0, albo 1, albo 2. 
Jak wylosuje zero, nic się nie dziaje, bierzemy do spektrum kolejny oligo o długości dokładnie k, przesuwamy okno wycinania o jedną pozycję w prawo. I znowu losujemy wartośc 1, 2 lub 3, i załóżmy, że tym razem wylosowało nam się 2 (czyli dokładnie tyle co delta_k). Wtedy (zawsze gdy wylosujemy coś innego niz zero) przeprowadzamy od razu drugie losowanie, np. między 0 a 1. A chodzi o wylosowanie znaku delty: dodatnia, czy ujemna. Załóżmy, że jak wylosuje się 0, to jest -, a jak 1 to +. Powiedzmy że wylosowało nam się 1, czyli plus. Czyli mamy efektywnie +2. Czyli w tym kroku nie wycinamy do spektrum oligo o długości k, ALE o długości k+2. I o takiej długości łańcuch liter idzie do spektrum. Następnie przesuwamy się o 1 w prawo i kontuujemy do końca. 
Uwaga techniczna: musicie zabezpieczyć wasz algorytm pod koniec, bo np. jeżeli jesteśmy już na samym końcu DNA, czyli na ostatnich k literach, to losowanie delta_k nie ma sensu. Najlepiej założyć, że mając dane k i delta_k > 0, jeżeli jesteśmy na przed-przed ostatniej pozycji (czyli do końca zostało dokładnie k+2 liter), to już wtedy w deltę się nie bawimy. Jeszcze innymi słowy: założmy, że pierwszy oligo idący do spektrum jest na pozycji bezwględnej 0, drugi na 1, trzeci na 2,... i trzy ostatnie są na zupełnie przykładowo wymyślanych przeze mnie teraz pozycjach: 188, 189, i 190. Wtedy, jeżeli delta_k podana przez użytkownika jest większa o zera (i nie ważne czy 1 czy 2), to bawimy się skracanie-wydłużanie oligonukleotydów tylko na pozycjach od 1 (czyli druga, bo liczymy od zera) do 187 (włącznie) i wszystkie pomiędzy. Pozycję 0 (pierwszy oligo) oraz 188, 189, 190 (trzy ostatnie z przykładu) zostawiamy zawsze w spokoju i te oligonukeotydy idą do spektrum zawsze mając długość k.
Ten wielki akapit od delta_k sugeruję przeczytać spokojnie i powoli przynajmniej dwukrotnie, zanim zaczniecie mnie Państwo męczyć mailami :)




W zasadzie, to niech program po wybraniu opcji "Generuj ręcznie" (w podmenu generatora instancji) zacznie od pytania, czy instancja problemu ma być standardowa. Wciśnięcie T (od tak) spowoduje wygenerowanie jej z parametrami domyślnymi i pytanie czy zapisać do pliku.
UWAGA: zapis do pliku jest opcjonalny, sam program, nawet jeżeli nie każemy zapisywać do pliku, ma oczywiście pamiętać ostatnią wygenerowaną instancję. Po wygenerowaniu wracamy do menu głównego. Jeżeli jest jakaś instancja w pamięci, niech nad nim wyświetli się o niej krótkie info, czyli parametry, np. "n = 450, k=8, delta_k = 0, ..." itd.

W menu Algorytmu naiwnego oraz Metaheurystyki (jeśli jest) już dowolność jeżeli chodzi o opcje. Zapewne będą mieć jakieś parametry sterujące ich pracą (metahuerystyka zawsze ma sporo, a i w naiwnym się zawsze jeden czy dwa parametry pracy da znaleźć i określić).

Po wykonaniu zadania program ma wyświetlić miarę Levenshteina pomiędzy oryginalnym DNA a tym zrekonstruowanym, napisać ile elementów (+ procent) spektrum się znalazło w rekonstrukcji, i zapytać czy zapisać wynik do pliku. Na wynik ma się składać (w pliku tekstowym, jednym) - oryginalne DNA, zrekonstruowane DNA, miara Levenshteina, a na samym dole wszystkie parametry instancji problemu.



****************************************************************************
[2024.11.04]

f. celu dla mateheurystyki:

Mamy dwa rozwiązania, i chcemy je ze sobą porównać, aby porównując te pary stworzyć jakiś ranking, od najlepszego do najgorszego. JEDNAK NIE MAMY DOSTĘPU DO ROZWIĄZANIA/SEKWENCJI ORYGINALNEJ (tj. udajemy, że nie mamy). Ranking przez to nie będzie w 100% dokładny (delikatnie mówiąc), ale zależy nam, żeby "trochę bardziej miał rację niż się mylił".

Kryteria:

- rozwiązanie, które używa większej liczby łuków o wadze 1, jest lepsze.
- rozwiązanie, które używa większej części grafu jest lepsze.

Dwa powyższe idą do pewnego stopnia w parze, więc trzeba je wyważyć. Można np. najpierw porównać liczbę łuków, a jak jest taka sama, to wtedy porównujemy pokrycie grafu.

- rozwiązanie, które używa większej liczby łuków o wagach 2 lub 3 jest gorsze (od tego, co używa ich mniej razy, rzecz jasna).
- gdy nie ma łuków w wadze 2 lub 3 (bo np. brak błędów negatywnych), to możemy oceniać ile wierzchołków zostało odwiedzonych wielokrotnie. Zakładająć, że błędy negatywne wynikające z powtórzeń są zawsze rzadkim wyjątkiem, im więcej razy dane rozwiązanie używa tych samych wierzchołków w ramach ścieżki w grafie, tym gorzej dla niego.

Porada ogólna: jak metahuerystyka ma problem z instancjami gdzie brak błędów negatywnych, można dodać jednak łuki o wadze 2 (i tylko takie) do grafu, i oceniać negatywnie rozwiązania które je używają.

Algorytm Dijskry (moduł nr 2 projektu) a ACO (alg. mrówkowy). Można wprowadzić parametr, że jakiś procent populacji mrówek, co np. 50 wierzchołków (też parametr, ile ich ma być) używa Dijskry aby przejść z punktu A do B w grafie. I zobaczyć, jak to wpływa na macierz feromonową i ogólną jakość rozwiązań.