Univerzita Karlova v Praze Matematicko-fyzikální fakulta
DIPLOMOVÁ PRÁCE
Zden¥k Pátek
Multiple sequence alignment pomocí genetických algoritm·
Kabinet software a výuky informatiky
Vedoucí diplomové práce: RNDr. Franti²ek Mráz, CSc.
Studijní program: Informatika
Studijní obor: Teoretická informatika
Praha 2012
D¥kuji RNDr. Franti²ku Mrázovi, CSc., za odborné vedení této práce a svým blízkým za stálou podporu.
Prohla²uji, ºe jsem tuto diplomovou práci vypracoval samostatn¥ a výhradn¥
s pouºitím citovaných pramen·, literatury a dal²ích odborných zdroj·.
Beru na v¥domí, ºe se na moji práci vztahují práva a povinnosti vyplývající ze zákona £. 121/2000 Sb., autorského zákona v platném zn¥ní, zejména skute£nost, ºe Univerzita Karlova v Praze má právo na uzav°ení licen£ní smlouvy o uºití této práce jako ²kolního díla podle 60 odst. 1 autorského zákona.
V Praze dne 6.4.2012 Zden¥k Pátek
Název práce: Multiple sequence alignment pomocí genetických algoritm·
Autor: Zden¥k Pátek
Katedra: Kabinet software a výuky informatiky
Vedoucí diplomové práce: RNDr. Franti²ek Mráz, CSc.
Abstrakt: Tato práce se zabývá problémem multiple sequence alignment (MSA).
Obsahuje návrh metody MSAMS, která umoº¬uje vyhledat motify v biologic- kých sekvencích, roz²t¥pit sekvence do blok· podle t¥chto motif·, vy°e²it MSA na blocích a nakonec sloºit globální alignment ze zarovnaných blok· a nalezených motif·. Hledání motif· i °e²ení MSA se provádí pomocí genetických algoritm·.
Práce dále popisuje implementaci metody MSAMS ve stejnojmenném programu, nastavení jeho parametr·, testování na databázi BAliBASE a porovnání s progra- mem ClustalW. Experimentální výsledky ukázaly, ºe MSAMS dokáºe najít lep²í alignmenty neº ClustalW.
Klí£ová slova: multiple sequence alignment, hledání motif·, genetické algoritmy, ClustalW
Title: Multiple sequence alignment using genetic algorithms Author: Zden¥k Pátek
Department: Department of Software and Computer Science Education Supervisor: RNDr. Franti²ek Mráz, CSc.
Abstract: The thesis adresses the problem of multiple sequence alignment (MSA).
It contains the specication of the proposed method MSAMS that allows to nd motifs in biological sequences, to split sequences to blocks using the motifs, to solve MSA on the blocks and nally to assemble the global alignment from the aligned blocks and motifs. Motif search and MSA are both solved using genetic algorithms. The thesis describes the implementation of the method, conguration of its settings, benchmarking on the BAliBASE database and comparison to the ClustalW program. Experimental results showed that MSAMS can discover better alignments than ClustalW.
Obsah
Úvod 3
1 Úvod do biologických struktur 5
1.1 DNA . . . 5
1.2 RNA . . . 6
1.3 Proteiny . . . 6
2 Genetické algoritmy 7 3 Úvod do Multiple sequence alignmentu 9 3.1 Sequence alignment . . . 9
3.2 Párový alignment . . . 10
3.3 Multiple sequence alignment . . . 11
3.4 Dynamické programování . . . 11
3.5 Progresivní algoritmy . . . 11
3.6 Genetické algoritmy . . . 12
3.7 Dal²í metody . . . 13
4 Hledání motif· 15 5 Metoda MSAMS 17 5.1 Popis metody MSAMS . . . 18
5.2 GAMotifSearch . . . 20
5.2.1 Reprezentace . . . 20
5.2.2 Algoritmus . . . 20
5.2.3 Parametry . . . 21
5.2.4 Genetické operátory . . . 22
5.3 GASequenceAlignment . . . 24
5.3.1 Reprezentace . . . 24
5.3.2 Algoritmus . . . 24
5.3.3 Parametry . . . 25
5.3.4 Inicializace jedinc· . . . 25
5.3.5 Ú£elová funkce . . . 26
5.3.6 Genetické operátory . . . 26
5.3.7 Roz²í°ení algoritmu kmenovým uspo°ádáním . . . 28
6 Nastavení parametr· metody MSAMS 29 6.1 Nastavení parametr· programu MSAMS . . . 29
6.2 Nastavení parametr· metody GAMotifSearch . . . 30
6.3 Nastavení parametr· metody GASequenceAlignment . . . 30
7 Implementace metody MSAMS 32 7.1 Implementace batchrunner.exe . . . 32
7.2 Implementace ClustalW . . . 32
7.3 Implementace GAMotifSearch . . . 33
7.4 Implementace GASequenceAlignment . . . 34
7.5 Implementace MSAMS . . . 35
7.6 Implementace score.exe . . . 36
7.7 Úpravy programu MSAMS . . . 36
7.7.1 Zm¥na programu °e²ícího MSA . . . 36
7.7.2 Zm¥na skórovací funkce . . . 37
7.7.3 Zm¥na programu na inicializaci genetického algoritmu v GA- SequenceAlignment . . . 37
7.7.4 Implementace nového genetického operátoru . . . 37
8 Ukázka pouºití programu MSAMS 39 9 Testování a výsledky 43 9.1 BAliBASE . . . 43
9.2 Testování programu MSAMS . . . 45
9.3 Hodnocení alignment· . . . 47
9.4 Výsledky bez pouºití hledání motif· . . . 47
9.5 Výsledky s pouºitím hledání motif· . . . 49
9.6 asová náro£nost . . . 51
9.6.1 asová náro£nost GASequenceAlignment . . . 51
9.6.2 asová náro£nost GAMotifSearch . . . 54
Záv¥r 55
Seznam pouºité literatury 57
Uºivatelská dokumentace programu MSAMS 59
Úvod
Bioinformatika je v¥dní obor, který se zabývá získáváním, skladováním, analýzou a interpretací molekulárních biologických dat. V sou£asné dob¥ se tento obor roz- víjí velice intenzívn¥ to je zp·sobeno zejména praktickou pot°ebou v molekulární biologii, proteomice, experimentální a klinické medicín¥, genetickém inºenýrství a farmacii.
Tato práce se zbývá úlohou multiple sequence alignment (MSA, vícenásobný alignment), která v bioinformatice hraje klí£ovou roli. Na jejím °e²ení totiº zá- visí mnoho dal²ích bioinformatických i biologických metod výsledky MSA se pouºívají nap°íklad p°i konstrukci fylogenetických strom·, rozpoznávání funk£n¥
d·leºitých míst v biologických sekvencích, predikci sekundární a terciární struktu- ry protein·, porovnávání regula£ních oblastí gen·, ur£ování gen· a zji²t¥ní jejich náchylnosti na mutace. Postupn¥ se °e²í stále sloºit¥j²í úlohy, a proto jsou kladeny vy²²í poºadavky i na výsledky MSA. Z toho d·vodu se na vývoj metod °e²ících MSA v¥nuje v sou£asné dob¥ mnoho prost°edk· a zna£né úsilí.
MSA se zabývá hledáním optimálního zarovnání biologických sekvencí, je to tedy optimaliza£ní úloha. Na její °e²ení jsem se v této práci rozhodl aplikovat metodu zvanou genetické algoritmy. Genetické algoritmy [1] jsou optimaliza£ní techniky napodobující p°írodní evoluci. Jsou inspirovány evolu£ními mechanismy dob°e fungujícími v p°írod¥ uº milióny let (nap°íklad d¥di£ností, k°íºením a p°iro- zenou selekcí). Genetické algoritmy p°isp¥ly k vytvo°ení velice ú£inných nástroj·, které slouºí p°i °e²ení mnohých praktických optimaliza£ních problém·. Byly jiº také vyuºity na °e²ení MSA v metod¥ SAGA [2].
MSA je velmi náro£ná úloha, proto je kaºdé její zjednodu²ení velice vítané.
V této práci jsem navrhl ²t¥pení úlohy pomocí p°edem nalezených vzor·, tzv.
motif·. To sice p°íli² nesníºí £asovou náro£nost MSA, ale m·ºe vést k získání kvalitn¥j²ích výsledk·. Hledání motif· je rovn¥º optimaliza£ní úloha, proto jsem na její °e²ení pouºil op¥t genetické algoritmy. P°edpokládal jsem, ºe díky jejich optimaliza£ní síle a robustnosti je bude moºné úsp¥²n¥ vyuºít jak na hledání motif·, tak na MSA.
Implementací vý²e popsaných metod vznikl program MSAMS, který umoº¬uje
°e²it problém MSA pouºitím r·znorodých technik:
• hledání motif· pomocí genetických algoritm·,
• ²t¥pení úlohy MSA podle motif·,
• °e²ení MSA pomocí genetických algoritm·,
• °e²ení MSA programem ClustalW [3],
• °e²ení MSA pomocí genetických algoritm· inicializovaných programem ClustalW.
Text práce obsahuje úvod do biologických struktur (kapitola 1), stru£ný po- pis genetických algoritm· (kapitola 2), úvod do problematiky MSA (kapitola 3) a hledání motif· (kapitola 4), popis, nastavení parametr· a implementaci mnou navrºené metody MSAMS °e²ící MSA (kapitoly 5, 6 a 7), ukázku jejího pouºití
(kapitola 8) a testování na benchmarkových zadáních (kapitola 9). Záv¥r práce shrnuje dosaºené výsledky a popisuje dal²í moºnosti rozvoje metody MSAMS.
K práci je p°iloºeno CD obsahující program MSAMS v£etn¥ zdrojového kódu, jeho dokumentaci (uºivatelská dokumentace je téº v p°íloze) a ve²keré výsledky, kterých bylo dosaºeno p°i testování.
1. Úvod do biologických struktur
Tato kapitola nabízí stru£ný úvod do biologických struktur, které se v rámci bioinformatiky zpracovávají. Podkapitola 1.1 popisuje molekulu DNA, kapitola 1.2 RNA a kapitola 1.3 proteiny.
Nejd·leºit¥j²í pojem pro tuto práci je biologická sekvence. Biologická sekven- ce, dále jen sekvence, je °et¥zec symbol·, formáln¥ denovaný následovn¥:
Denice. Nech´Σje abeceda al ∈N. Paks=s1s2...sl, kde proi= 1, ..., l:si ∈ Σ, je sekvence délky l.
Pro ú£ely této práce je pot°eba popsat t°i druhy sekvencí sekvenci DNA (popi- sující primární strukturu molekuly DNA, podrobn¥ji v podkapitole 1.1), sekvenci RNA (popisující primární strukturu molekuly RNA, podrobn¥ji v podkapitole 1.2) a proteinovou sekvenci (popisující primární strukturu proteinu, podrobn¥ji v podkapitole 1.3).
Sekvence je moºné uchovávat v r·zných formátech v této práci vyuºívám formát FASTA [4]. Soubor formátu FASTA je textový soubor, který m·ºe obsa- hovat více sekvencí p°ed kaºdou sekvencí je °ádek s popisem sekvence uvozený znakem > a na následujících °ádcích je vlastní sekvence. P°íklad souboru ve formátu FASTA je na za£átku kapitoly 8.
1.1 DNA
Deoxyribonukleová kyselina (DNA) je makromolekula v podob¥ °et¥zce nukle- otid·, typicky uspo°ádaných do struktury dvou²roubovice. Kaºdý nukleotid se skládá z deoxyribózy, fosfátové skupiny a jedné ze £ty° nukleových bází (adenin, cytosin, guanin a thymin).
U prokaryotických organism· se DNA nachází v bun¥£né cytoplazm¥, u eu- karyotických je v¥t²inou uloºena uvnit° jader bun¥k. DNA je nezbytná pro ºi- vot, protoºe kóduje informace pot°ebné pro syntézu protein· a tvorbu bu¬e£ných struktur a tím i vývoj a vlastnosti celého organismu.
Struktura molekuly DNA se popisuje na £ty°ech úrovních:
1. Primární struktura ur£uje po°adí bází v molekule DNA. Primární struktu- ra DNA hraje klí£ovou roli p°i syntéze protein·, protoºe se podle ní vytvá°í mediátorová RNA, podle které se poté sestavuje protein.
2. Sekundární struktura popisuje zp·sob párování bází pomocí vodíkových m·stk· (v dvou²roubovici DNA se typicky páruje adenin s thyminem a cyto- sin s guaninem). Sekundární struktura se podílí na správné funkci molekuly.
3. Terciární struktura popisuje prostorové uspo°ádání celé molekuly DNA v bu¬ce. Terciární struktura je d·leºitá pro funkci a stabilitu molekuly.
4. Kvartérní struktura poskytuje informace o interakcích mezi molekulami DNA, RNA a proteiny.
Sekvence DNA popisuje primární strukturu molekuly DNA pomocí abecedyΣ = {A, C, G, T} [5]. A zna£í adenin, C cytosin, G guanin a T thymin.
Sekvence se z molekul DNA £tou pomocí procesu sekvenování. Kv·li nedoko- nalosti sekvenovacích metod byly do abecedy sekvencí DNA p°idány symboly pro neúpln¥ specikované báze (B, D, H, K, M, N, R, S, V, W, Y) [6].
1.2 RNA
Ribonukleová kyselina (RNA) je molekula skládající se z °et¥zce nukleotid·. Od DNA se li²í p°ítomností hydroxylové skupiny v kaºdém nukleotidu a nahrazením nukleové báze thymin uracilem. RNA je syntetizována podle struktury DNA po- mocí enzym·. Narozdíl od DNA vytvá°í nej£ast¥ji krat²í jednoduchá vlákna. RNA plní v organismu mnoho funkcí m·ºe nést genetickou informaci, katalyzovat bi- ologické reakce, nést informací o struktu°e vytvá°ených protein·, transportovat aminokyseliny, regulovat genovou expresi a vykonávat splicing DNA.
Strukturu RNA lze stejn¥ jako DNA popsat na £ty°ech úrovních. Sekvence RNA je °et¥zec z abecedy Σ = {A, C, G, U} (U zna£í uracil) reprezentující pri- mární strukturu molekuly RNA. Op¥t se mohou do abecedy p°idat symboly pro neúpln¥ specikované báze.
1.3 Proteiny
Protein je vysokomolekulární látka skládající se z °et¥zce aminokyselin. Existuje 22 r·zných aminokyselin, které mohou být obsaºeny v proteinech. Proteiny jsou základem v²ech ºivých organism·. Následující seznam ukazuje r·zné funkce, které proteiny plní (p°íklady protein· jsou v závorkách):
• katalýza biologických reakcí (enzymy),
• ochrana organismu (brinogen, imunoglobuliny),
• regula£ní a °ídící funkce (hormony, receptory),
• stavební funkce (keratin, kolagen),
• transport a skladování látek (hemoglobin) a
• pohyb (aktin, myosin).
Biochemické vlastnosti proteinu jsou ur£eny jeho strukturou. Ta se op¥t rozd¥luje na £ty°i úrovn¥:
1. Primární struktura po°adí aminokyselin v proteinovém °et¥zci.
2. Sekundární struktura lokální prostorové uspo°ádání proteinu.
2. Genetické algoritmy
Genetické algoritmy [1] jsou globální optimaliza£ní metody, které jsou inspirovány evolu£ními mechanismy p°írody. Mezi jejich hlavní p°ednosti spadají robustnost, vysoký výkon, jednoduchá implementace, moºnosti paralelizace a schopnost op- timalizovat rozli£né druhy ú£elových funkcí. Genetické algoritmy byly v praxi úsp¥²n¥ pouºity na mnoho optimaliza£ních problém·, nap°íklad:
• návrh vodovod·,
• optimalizace parametr· motoru letadla Boeing 777,
• problém obchodního cestujícího,
• rozpoznávání obli£eje zlo£inc· a
• u£ení neuronové sít¥.
Genetické algoritmy optimalizují ú£elovou funkci, n¥kdy téº nazývanou tness funkce.
Denice. Funkce f :D7−→H, kdeH ⊆R, je ú£elová funkce.
Deni£ní obor D m·ºe obsahovat jakékoliv prvky, obor hodnot H je vºdy pod- mnoºina reálných £ísel. Ú£elové funkce mohou být funkce vyjád°itelné analyticky, ale také se mohou po£ítat n¥jakým algoritmem, ur£it jako výsledek simulace ne- bo zm¥°it fyzickým za°ízením. Hodnota ú£elové funkce prvku zD je úm¥rná jeho kvalit¥. Cílem optimaliza£ního procesu je najít prvek zD, na n¥mº zadaná ú£elo- vá funkce dosahuje optimální (podle volby minimální nebo maximální) hodnoty.
Takový prvek se nazývá globální optimum ú£elové funkce (tedy bu¤ globální minimum nebo globální maximum ú£elové funkce).
e²ení (mnoºina vstupních prom¥nných) ú£elové funkce je v genetických al- goritmech reprezentováno jedincem. Na jedince lze také nahlíºet jako na bod v deni£ním oboru ú£elové funkce. Kaºdého jedince lze ohodnotit ú£elovou funk- cí jeho hodnota je rovna hodnot¥ ú£elové funkce v bod¥, který je reprezentován tímto jedincem. Kone£ná mnoºina jedinc· se nazývá populace.
Samotná optimalizace je itera£ní proces. Nejprve je vytvo°ena po£áte£ní po- pulace jedinc· (nap°íklad jako mnoºina náhodn¥ generovaných bod· v deni£ním oboru ú£elové funkce). V kaºdé iteraci dochází ke vzniku nových jedinc· pomo- cí genetických operátor· (nap°íklad k°íºení a mutace) s cílem najít nová a lep²í
°e²ení daného problému. Genetické operátory bývají navrºeny na míru optima- lizovanému problému. Z p·vodních a nových jedinc· je selek£ním operátorem vybrána nová populace a algoritmus pokra£uje dal²í iterací. Selekce má za úkol zajistit p°eºití dobrých jedinc· a zárove¬ zachovat diverzitu populace, aby ne- zkonvergovala p°ed£asn¥ do lokálního optima. Selekce se n¥kdy také pouºívá na výb¥r jedinc·, kte°í podstoupí genetické operace. Optimaliza£ní proces je zasta- ven po spln¥ní ukon£ovacího kritéria nap°íklad po uplynutí p°id¥leného £asu, po provedení zadaného po£tu iterací nebo po konvergenci populace do jednoho
bodu v deni£ním oboru ú£elové funkce. Obecné schéma genetických algoritm·
vypadá následovn¥:
Inicializuj a ohodno´ populaci X
while ukon£ovací kritérium není spln¥no do
Y ←Vytvo° populaci potomk· z X pomocí genetických operátor·
Ohodno´ Y ú£elovou funkcí
X ← Selekcí vyber novou populaci z X a Y endVra´ nejlep²ího jedince z X
P°i implementaci genetických algoritm· je t°eba navrhnout vhodnou reprezentaci problému pomocí jedinc·, naprogramovat fungující genetické operátory, vybrat vyhovující selek£ní operátor a ukon£ovací kritérium. P°ed spu²t¥ním genetického algoritmu je typicky nutné nastavit správn¥ jeho parametry nap°íklad zvý²ením velikosti populace lze £asto docílit lep²ích výsledk·, ale za cenu prodlouºení doby optimalizace.
Optimalizace genetickými algoritmy nezaru£uje nalezení skute£ného globální- ho optima ú£elové funkce stává se, ºe se algoritmus zastaví v lokálním optimu.
V praxi není £asto moºné zjistit, zda bylo nalezeno globální optimum nebo pouze lokální. Mnoha aplikacím v²ak sta£í nalezení suboptimálního °e²ení, pokud je ho dosaºeno v rozumném £ase.
3. Úvod do Multiple sequence alignmentu
Jak bylo °e£eno v úvodu, multiple sequence alignment (MSA, vícenásobný alig- nment) je jednou z prioritních bioinformatických úloh. Zárove¬ je v²ak obtíºn¥
°e²itelný kv·li vysoké výpo£etní náro£nosti, proto se výzkumem algoritm· °e²í- cích MSA zabývá mnoho v¥dc· po celém sv¥t¥. Bylo vyvinuto velké mnoºství metod li²ících se p°ístupem, £asovou a pam¥´ovou náro£ností a kvalitou naleze- ných °e²ení. Následující podkapitola 3.1 se zabývá obecným sequence alignmen- tem a obsahuje pot°ebné denice. Dal²í podkapitoly 3.2 aº 3.7 popisují nejprve zarovnávání dvou sekvencí (párový alignment), dále MSA a nakonec jsou p°ed- staveny r·zné metody °e²ící MSA. Vzhledem k zam¥°ení této práce je podrobn¥ji popsáno vyuºití genetických algoritm· v podkapitole 3.6.
3.1 Sequence alignment
Sequence alignment je bioinformatická úloha, která spo£ívá v nalezení co nejlep-
²ího zarovnání (alignmentu) biologických sekvencí. Alignment je tvo°en dv¥ma a více sekvencemi, do kterých jsou vloºeny mezery, a je denován takto:
Denice. Nech´ S = (s1, s2, ..., sN) je N-tice sekvencí nad abecedou Σ, N ≥ 2. Alignment A = (a1, a2, ..., aN) je N-tice sekvencí stejné délky l, kde pro i = 1, ..., N :ai je sekvence nad abecedouΣ∪ {−}délkyl, která vznikla zsi vloºením n¥jakého (p°ípadn¥ nulového) po£tu symbol· mezery −.
Aij zna£í j-tý znak i-té sekvence alignmentu A. Alignment je typicky znázorn¥n jako matice o N °ádcích, coº ukazuje následující p°íklad zarovnání t°í sekvencí DNA.
DNA sekvence p°ed zarovnáním:
AACTCGAAACCTGC AAACTGCCACCTCCAG GACTTCGCCTCACT Po zarovnání:
-AACT-CGAAACCTGC--- AAACTGCC--ACCT-CCAG G-ACTTCG---CCT-CACT
Více mezer za sebou tvo°í díru:
Denice. Díra je posloupnost mezer v jedné sekvenci, která je z obou stran ohrani£ena bu¤ symbolem abecedyΣ nebo za£átkem nebo koncem sekvence.
Cílem je najít takový alignment, ze kterého lze rozpoznat a porovnat shodné a podobné £ásti zarovnávaných sekvencí, které jsou d·sledkem jejich funk£ní,
strukturní nebo evolu£ní p°íbuznosti. Kvalitativní ohodnocení nalezeného align- mentu je biologický problém záleºí na tom, jaké sekvence zarovnáváme, zda jsou k dispozici dal²í informace o zarovnávaných sekvencích (nap°íklad sekun- dární nebo terciární struktura proteinu) a k £emu se bude alignment pouºívat.
Podle ú£elu alignmentu lze poºadovat bu¤ globální alignment (cílem je zarovnat v²echny znaky ve v²ech sekvencích) nebo lokální alignment (cílem je najít a za- rovnat podobné £ásti sekvencí). V celém následujícím textu bude alignmentem my²len globální alignment. Biologickou kvalitu alignmentu není moºné objektiv- n¥ hodnotit, proto se nahrazuje skórovací funkcí. Ta pro daný alignment spo£ítá hodnotu, která je vy²²í pro kvalitn¥j²í alignment. Dal²í podkapitola se zabývá párovým alignmentem a zejména jeho ohodnocováním pomocí skórovací funkce.
3.2 Párový alignment
Párový alignment (pairwise sequence alignment) je zarovnávání dvou sekvencí. Na ohodnocení kvality alignmentu A = (a1, a2) délky l se £asto pouºívá následující skórovací funkce:
score(a1, a2) =
l
X
k=1
M(a1k, a2k) +GapPenalty(a1) +GapPenalty(a2).
M je pouºitá substitu£ní matice, která udává podobnost mezi jednotlivými sym- boly abecedy zarovnávaných sekvencí.M(a1k, a2k)je podobnost mezik-tým sym- bolem sekvence a1 a k-tým symbolem sekvence a2. Substitu£ní matice m·ºe být roz²í°ena na skórovací matici, která navíc obsahuje míru podobnosti mezi sym- boly abecedy zarovnávaných sekvencí a symboly mezery (pokud není roz²í°ená, pak se p°edpokládá, ºe je tato míra rovna 0). V p°ípad¥ proteinových sekvencí se na ur£ení míry podobnosti mezi jednotlivými aminokyselinami pouºívají r·zné substitu£ní matice, nap°íklad PAM [8] nebo BLOSUM [9], v p°ípad¥ DNA nebo RNA sekvencí lze pouºít nap°íklad jednotkovou matici.
GapPenalty je funkce udávající pokutu sekvence za díry. V¥t²inou se pouºívá konstantní, lineární nebo anní penalizace za díry:
• konstantní penalizace GapPenalty(a) = P
d∈Ddpenalty, kdeDje mnoºina v²ech d¥r v sekvenci a adpenalty je p°edem zvolená pokuta za díru,
• lineární penalizace GapPenalty(a) = P
m∈Mmpenalty, kdeM je mnoºina v²ech mezer v sekvencia a mpenalty je p°edem zvolená pokuta za mezeru,
• anní penalizace GapPenalty(a) = P
d∈Ddpenalty+P
m∈Mmpenalty. Volba GapPenalty závisí na pouºité substitu£ní matici, zarovnávaných sek- vencích a na ú£elu alignmentu. Nap°íklad p°i zarovnávání del²ích proteinových sekvencí s neznámou podobností je vhodné pouºít matici BLOSUM62 a zvolit
3.3 Multiple sequence alignment
Multiple sequence alignment (MSA) se zabývá zarovnáváním t°í a více sekvencí.
V¥t²inou se pouºívá na zarovnávání skupiny sekvencí, u kterých se p°edpokládá evolu£ní p°íbuznost organismy, ze kterých sekvence pocházejí, jsou vývojovými potomky spole£ného p°edka. Úkolem MSA je, podobn¥ jako v p°ípad¥ párového alignmentu, najít oblasti podobnosti mezi sekvencemi pomocí jejich zarovnání.
Plánované pouºití alignmentu ur£uje, jak se má hodnotit jeho kvalita. Hodnocení kvality se op¥t nahrazuje skórovací funkcí. Tu lze nap°íklad vytvo°it modikací d°íve uvedené skórovací funkce pro párový alignment takto:
score(A) =
N−1
X
i=1 N
X
j=i+1
score(ai, aj).
Pouºívají se i jiné skórovací funkce, nap°íklad norMD [12], která do výsledného skóre zahrnuje dodate£né informace o zarovnávaných sekvencích. Zadání MSA se mohou li²it typem sekvencí, po£tem sekvencí, délkou sekvencí a mírou jejich identity. V následujících podkapitolách jsou popsány vybrané metody °e²ící MSA.
N¥které mohou být vhodn¥j²í neº jiné na r·zné typy zadání, proto je p°i °e²ení MSA velice d·leºité vybrat správný program. Podrobný návod existuje v [13].
3.4 Dynamické programování
P°esné (optimální) °e²ení MSA lze najít pomocí dynamického programování. To se v²ak dá pouºít p°i zarovnávání nejvý²e t°í sekvencí, protoºe prohledávací pro- stor se zv¥t²uje exponenciáln¥ s po£tem zarovnávaných sekvencí p°ímá aplikace dynamického programování ro²í°ením algoritmu Needleman-Wunsch pouºitá na
°e²ení MSA o N sekvencích má £asovou sloºitost O(l1·l2·...·lN), kde li je délka i-té sekvence.
Na základ¥ dynamického programování byl vyvinut program MSA [14], coº je heuristická implementace dynamického programování, která umoº¬uje zarovnat aº deset sekvencí. Jeho nadstavba DCA dokáºe pomocí chytrého ²t¥pení sekvencí zpracovat 20 aº 30 sekvencí. Programy dokáºou najít vysoce kvalitní °e²ení, to je v²ak vyváºeno jejich vysokou £asovou i pam¥´ovou náro£ností.
3.5 Progresivní algoritmy
Progresivní algoritmy se t¥²í veliké oblib¥ díky jejich nízké £asové a pam¥´ové ná- ro£nosti. Nejznám¥j²ím zástupcem je program ClustalW [3]. Jeho základní verze
°e²í MSA ve t°ech fázích:
1. Vytvo°í se párový alignment v²ech dvojic sekvencí v zadání a spo£ítá se matice podobnosti (ta obsahuje míru podobnosti mezi v²emi dvojicemi sek- vencí).
2. Spo£ítá se fylogenetický strom (guide tree) pomocí matice podobnosti.
3. Celkový alignment vznikne pomocí postupných párových alignment· sek- vencí podle fylogenetického stromu.
Program ClustalW dále obsahuje r·zná zlep²ení zvy²ující jeho výkon p°i °e²ení MSA:
• fylogenetický strom lze vytvá°et bu¤ algoritmem Neighbour Joining nebo pomocí rychlej²ího UPGMA,
• itera£ní schéma umoº¬uje vylep²it alignment postupným p°erovnáváním jednotlivých sekvencí,
• je moºné vyuºít informace o sekundární struktu°e proteinu pomocí úpravy penaliza£ních parametr·,
• hodnoty penaliza£ních parametr· jsou dále ovlivn¥ny výb¥rem substitu£- ní matice, podobností sekvencí, délkou sekvencí, rozdílem délek sekvencí a konkrétními bázemi nebo aminokyselinami v sekvencích.
3.6 Genetické algoritmy
V roce 1996 byl vyvinut první program °e²ící MSA, který vyuºíval genetické algo- ritmy SAGA [2]. Program pracuje podle schématu podobnému tomu z kapitoly o genetických algoritmech. Prvním krokem algoritmu je vytvo°ení populace se 100 jedinci. Kaºdý jedinec reprezentuje jeden alignment, který je na po£átku tvo°en sekvencemi odsazenými o 0 aº 50 mezer. Ú£elová funkce na ohodnocení jedinc·
se po£ítá dle následujícího vzorce:
fitness(A) =
N−1
X
i=1 N
X
j=i+1
wi,j·f((Ai, Aj)).
N je po£et zarovnávaných sekvencí. wi,j je váha mezi i-tou a j-tou sekvencí, která závisí na podobnosti t¥chto sekvencí.f((Ai, Aj)) je skóre hodnotící kvalitu párového alignmentu mezii-tou aj-tou zarovnanou sekvencí tak, jak bylo ukázáno v podkapitole 3.2 (v metod¥ SAGA lze pouºít libovolnou substitu£ní matici a bu¤
lineární nebo anní penalizaci za díry).
V kaºdé iteraci programu se nahradí 50 nejhor²ích jedinc· novými jedinci. Ro- di£e nových jedinc· jsou vybráni pomocí stochastického univerzálního vzorkování [15]. Nový jedinec vznikne pouºitím náhodn¥ vybraného genetického operátoru z mnoºiny genetických operátor·, která je popsána dále. P°ípadné duplikáty se odstra¬ují. Program kon£í, pokud nedokázal zlep²it alignment v posledních 100 iteracích.
Operátory metody SAGA
Uniform crossover (uniformní k°íºení) v obou rodi£ích se nejprve naleznou dva konzistentní sloupce (konzistentní sloupec obsahuje stejné báze nebo amino- kyseliny a v obou rodi£ích reprezentuje stejné pozice v zarovnávaných sekvencích).
Operátorem vzniknou dva potomci, kte°í jsou kopiemi rodi£· aº na zam¥n¥né blo- ky mezi konzistentními sloupci.
Gap insertion (vkládání mezer) operátor rozd¥lí sekvence v alignmentu do dvou skupin, nap°íklad podle jejich podobnosti. Do kaºdé sekvence první skupiny vloºí díru pevné, p°edem náhodn¥ zvolené, délky na stejnou náhodn¥ zvolenou pozici. Poté vloºí díru stejné délky do v²ech sekvencí druhé skupiny na jinou po- zici, náhodn¥ zvolenou poblíº první pozice.
Block shuing (p°esouvání blok·) operátor má za úkol posouvat bloky mezer nebo aminokyselin uvnit° alignmentu. Bloky lze p°emis´ovat n¥kolika zp·soby:
• posunutím bloku doleva nebo doprava,
• horizontálním roz²t¥pením bloku a p°esunutím jedné £ásti doleva nebo do- prava,
• vertikálním roz²t¥pením bloku a p°esunutím jedné £ásti doleva nebo dopra- va.
Block searching (prohledávání blok·) operátor náhodn¥ vybere pod°et¥zec náhodné délky v jedn¥ ze sekvencí alignementu a postupn¥ ho vyhledá v ostatních sekvencích. Sekvence se posunou tak, aby byly vyhledané pod°et¥zce zarovnané ve sloupci. Hledání se neprovádí na celém alignmentu, ale pouze v okolí prvotního pod°et¥zce.
Local optimal or sub-optimal rearrangements (lokální p°eskupování) ope- rátor optimalizuje mezery v bloku, bu¤ pomocí úplného prohledávání (pokud sta£í prohledat mén¥ neº 2000 kombinací) nebo pomocí LAGA (local alignment genetic algorithm). Algoritmus LAGA funguje stejn¥ jako SAGA, ale obsahuje pouze dva genetické operátory jednobodové k°íºení a p°esouvání blok·. Velikost populace v LAGA je 20 jedinc·, po£et iterací je roven desetinásobku po£tu zarovnávaných sekvencí.
Metoda SAGA byla testována na r·zných datasetech [2], výsledky byly srov- natelné s programem ClustalW, ale doba b¥hu byla mnohem vy²²í to bylo z°ejm¥ zp·sobeno výpo£etn¥ náro£nými operátory (one-point crossover, uniform crossover, block searching, local rearrangements).
3.7 Dal²í metody
Existuje mnoho dal²ích metod na °e²ení MSA. Jako ukázka ²í°e vyzkou²ených p°í- stup· poslouºí následující seznam obsahující n¥které dosud nezmín¥né programy
°e²ící MSA:
• Dialign [16] pouºívá kombinaci hladového a progresivního algoritmu na za- rovnávání celých segment·,
• HMMER [17] pouºívá skryté Markovské modely,
• MAFFT [18] vyuºívá Fourierovu transformaci,
• ProbCons [19] kombinuje pravd¥podobnostní modelování a konzisten£ní techniky,
• Praline [20] hledá MSA pomocí prol· a umoº¬uje vyuºít informace o sekun- dární struktu°e protein·.
4. Hledání motif·
Motif je vzor v biologické sekvenci, který m·ºe korespondovat s funk£n¥ nebo strukturn¥ d·leºitou oblastí biologické sekvence. P°edpokládá se, ºe se tyto vzory
£asto zachovávají v pr·b¥hu evoluce a proto je lze najít v p°íbuzných sekven- cích. Vyhledávání motif· je jeden z fundamentálních problém· bioinformatiky pouºívá se p°i °e²ení MSA, p°i p°edpov¥di proteinových struktur, p°i detekci regula£ních oblastí v sekvencích a na charakterizaci skupin protein·.
Vyhledávání motif· je hledání p°edem neznámého vzoru (£asto pevn¥ dané délky l) v N biologických sekvencích. Motif se nemusí shodovat ve v²ech sek- vencích, proto je pot°eba speciální reprezentace. Nn¥které moºnosti reprezentace motifu jsou uvedeny dále.
Závorková notace
Závorková notace popisuje motify za pomoci symbol· pro báze, aminokyseliny, mezery, výb¥ry, opakování a negace. B¥ºn¥ se pouºívá notace z programu PRO- SITE [21], která umoº¬uje vyuºít následující elementy na popis motif·:
• x zna£í libovolnou bázi nebo aminokyselinu,
• sloºené závorky reprezentují negaci (nap°íklad{A}znamená libovolná ami- nokyselina krom¥ alaninu),
• hranaté závorky zna£í výb¥r (nap°íklad [ALV] znamená bu¤ alanin nebo leucin nebo valin),
• pomocí kulatých závorek lze zapsat opakování (nap°íkladA(3) znamená t°i výskyty alaninu za sebou,A(2,4)znamená 2 aº 4 výskyty alaninu za sebou),
• symbolem > lze ozna£it za£átek proteinové sekvence (N-terminus),
• symbolem < se zna£í konec sekvence (C-terminus).
Symbol − se v PROSITE pouºívá na odd¥lení jednotlivých £ástí motifu.
Proteinový motif zapsaný v notaci PROSITE m·ºe vypadat nap°íklad takto:
N{P}[KR]x(3)S
Vý²e napsaný vzor °íká, ºe motif obsahuje asparagin (kód N), následovaný ja- koukoliv aminokyselinou krom¥ prolinu (P), poté lysin (K) nebo arginin (R), následovaný t°emi libovolnými aminokyselinami a kon£í serinem (S).
Konsenzus
Výsledkem programu hledajícího motif v N sekvencích mohou být pouze pozice motifu v jednotlivých sekvencích. Vzhledem k tomu, ºe vzory nalezené v jednot- livých sekvencích £asto nejsou identické, ale obsahují neshody, je vhodné z nich vytvo°it konsenzus. Konsenzus je °et¥zec, který na kaºdé pozici obsahuje symbol, který se v nalezených vzorech vyskytuje s maximální frekvencí:
Denice. Nech´ vzory M1, ..., MN jsou °et¥zce délky l, pak konsenzus je °et¥- zec k = k1...kl, kde ∀i = 1, ..., l platí: ki je symbol vyskytující se s maximální frekvencí v multimnoºin¥ {M1i, ..., MN i}.
V následujícím p°íklad¥ jsou vzory nalezené v DNA sekvencích vyzna£eny vel- kými písmeny, vzory i konsenzus mají délku 6:
Sekvence 1: actgaactgcaaAATACGcatggtaca Sekvence 2: cagtttacgATTACGgacccacgtgac Sekvence 3: cgcatgAATAGGcgatcaacttgacaa Sekvence 4: actcggactgatAATTCGactgtgaca Pozice motifu: 13, 10, 7, 13
Konsenzus: AATACG Pozi£ní váhová matice
Pozi£ní váhová matice je popis výskyt· symbol· v motifu s pouºitím pravd¥po- dobnosti.
Denice. Pozi£ní váhová matice P velikosti l x |Σ| je matice, ve které je Pij rovno pravd¥podobnosti výskytu j-tého symbolu na i-té pozici motifu.Σ je abe- ceda obsahující v²echny symboly vyskytující se v prohledávaných sekvencích,l je délka motifu.
Následující p°íklad ukazuje pozi£ní váhovou matici pro motif délky 7 v sekvenci RNA:
1 2 3 4 5 6 7
A 1 0 0 0,15 0 0,3 0,9
C 0 0,85 0,8 0,05 0 0,15 0
G 0 0,15 0,2 0,05 1 0,15 0,05
U 0 0 0 0,75 0 0,4 0,05
Konsenzus motifu popsaného touto maticí je ACCUGUA.
5. Metoda MSAMS
MSA je sloºitá úloha a ºádná z existujících metod na její °e²ení není dokonalá.
Jednodu²²í zadání lze vy°e²it dob°e pomocí r·zných nástroj· (n¥které z nich jsou popsány v kapitole 3). Problémy typicky nastávají, kdyº je pot°eba zarovnat velký po£et sekvencí anebo jsou sekvence dlouhé.
Proto jsem vyvinul metodu, která umoº¬uje rozd¥lit sloºitá zadání MSA na ví- ce jednodu²²ích, které se °e²í nezávisle. t¥pení zadání se provádí pomocí p°edem nalezených motif· klí£ový p°edpoklad je, ºe nalezené motify si v jednotlivých sekvencích odpovídají, a proto je moºné je zarovnat p°ímo na sebe. Bloky sekven- cí mezi motify jsou op¥t úlohy MSA. Celý proces si lze p°iblíºit na jednoduchém p°íkladu, ve kterém se zarovnávají £ty°i sekvence DNA:
AACTGACTAGATTTACGGTACTGAG ACTGACTATAAATACGGGATCGAGAC ACGTGTGACTTAACAAGTGTACGA CAATGCATATATAATCTAGGGACGTAG
V tomto p°íklad¥ byly nalezeny dva motify o délce t°í bází, podle kterých se zadání roz²t¥pí motif TGA na pozicích 4, 3, 6 a 4 a motif GGT na pozicích 17, 16, 17 a 19. Po zarovnání motif· na sebe zbudou t°i nezarovnané bloky:
AAC TGA CTAGATTTAC GGT ACTGAG
AC TGA CTATAAATAC GGG ATCGAGAC
ACGTG TGA CTTAACAA GTG TACGA
CAA TGC ATATATAATCTA GGG ACGTAG
Nezarovnané bloky lze zarovnat pomocí n¥kterého z program· °e²ících MSA.
Nakonec je vytvo°en globální alignment celé p·vodní úlohy spojením jiº zarov- naných blok· a motif· tak, aby po°adí bází (nebo aminokyselin) z·stalo stejné jako v originálních sekvencích. Výsledek m·ºe vypadat nap°íklad takto:
AAC---TGACT-AGATT-TAC--GGT-ACTGAG-- A-C---TGACT-ATA-AATAC--GGG-ATCGAGAC A-CGTGTGACTTA-ACAA---GTGTAC-GA--- --CAA-TGCAT-ATATAAT-CTAGGG-ACGTAG--
Výhodou této metody je, ºe umoº¬uje najít kvalitní alignment sloºit¥j²ího zadání takového, které by se nepoda°ilo dob°e zarovnat bez rozd¥lení na podproblémy.
Dal²í výhodou je, ºe nalezené motify budou zarovnány vºdy p°ímo nad sebe to je velmi p°ínosné, pokud je kvalita pouºitých motif· p°edem ov¥°ena.
Tento p°ístup s sebou nese také ur£ité nevýhody. Pokud se pouºívá více r·z- ných motif· na ²t¥pení sekvencí, je nutné zajistit, aby se motify nek°íºily (jinak sekvence nelze rozd¥lit). M·ºe se také stát, ºe v optimálním globálním alignmen- tu nejsou pouºité motify zarovnány nad sebe, a pokud tyto motify pouºijeme na rozd¥lení úlohy, tak jiº nebude moºné optimálního alignmentu dosáhnout (i kdyº se poda°í zarovnat jednotlivé bloky optimáln¥).
Metoda MSAMS aplikující vý²e popsaný postup je popsána v následujících podkapitolách, kapitola 6 popisuje nastavení jejích parametr·, kapitola 7 se za- bývá její implementaci a kapitola 8 ukazuje její pouºití na konkrétním zadání.
5.1 Popis metody MSAMS
MSAMS (Multiple Sequence Alignment using Motif Search) je metoda vyvinutá na °e²ení MSA, která aplikuje rozklad MSA na podproblémy tak, jak je popsá- no v úvodu této kapitoly. Metoda tedy pracuje ve dvou fázích hledání motif·
a MSA. Ob¥ fáze jsou spustitelné nezávisle. Implementací MSAMS vznikl stejno- jmenný program.
V první fází se vyhledávají motify pomocí metody GAMotifSearch, popsa- né v sekci 5.2. První motif se vyhledává v celých vstupních sekvencích, poté se z nich odstraní (aby nemohl být znovu nalezen) a hledá se druhý motif, ten se op¥t odstraní a hledá se t°etí motif celkový po£et hledaných motif· je ur£en parametrem M SRuns. Pokud je úkolem najít pouze motify, nikoliv alignment, lze vynechat druhou fází (parametr M ode se nastaví na M OT IF). Výstupem jsou pak pouze pozice nalezených motif·.
V druhé fází probíhá zarovnávání blok· mezi nalezenými motify pomocí me- tody GASequenceAlignment, popsané v sekci 5.3. I druhou fázi je moºné spustit samostatn¥ (parametrM odese nastaví naALIGN). To vyuºijeme, pokud máme motify p°ipravené p°edem (nap°íklad ru£n¥ nebo pomocí jiného programu) nebo nechceme zadání ²t¥pit na podproblémy. Pro °e²ení MSA v druhé fázi lze alterna- tivn¥ pouºít program ClustalW (parametrM ethodse nastaví naCLU ST ALW).
Schematicky jde práci MSAMS popsat následovn¥:
Na£ti sekvence S
První fáze (hledání motif·):
if Mode ∈ {MOTIF,FULL} then T ←S
for i←1 to MSRuns do Pi ←GAMotifSearch(T) P ←P ∪Pi
T ← Odstra¬ motify na pozicích Pi z T end
P ← Spo£ítej pozice motif· P v S
elseNa£ti pozice p°edem p°ipravených motif· P end
P ← Set°i¤P
Druhá fáze (MSA):
Odstra¬ p°ek°íºené pozice motif· z P if Mode ∈ {ALIGN,FULL} then
B ←Roz²t¥p S na bloky na pozicích motif· P for ∀b∈B do
if Method =CLUSTALW then a←ClustalW(b)
else
a←GASequenceAlignment(b) end
A←A∪a end
G← Sloº globální alignment pomocí A a P Ohodno´ G
Vra´ G end
Program MSAMS umoº¬uje zarovnávat libovolné druhy sekvencí, jejich po£et a délka nejsou nijak omezeny. Vstupní a výstupní formát sekvencí je FASTA (popsán v kapitole 1). Parametry programu jsou vypsány v tabulce 1:
Parametr Obor hodnot Popis
ID °et¥zec identika£ní kód úlohy
Sequence °et¥zec soubor se zarovnávanými
sekvencemi
MS °et¥zec soubor s parametry pro pro-
gram GAMotifSearch
SA °et¥zec soubor s parametry pro
program GASequenceAlign- ment
MSRuns N po£et hledaných motif·
MotifFile °et¥zec soubor s ru£n¥ p°ipravený- mi pozicemi motif·
Mode {FULL,MOTIF,ALIGN} mód výpo£tu Method {GENETIC,CLUSTALW} metoda °e²ící MSA
CW °et¥zec soubor s parametry progra-
mu ClustalW
Score °et¥zec soubor s parametry skórova- cího programu
Tabulka 1. Parametry programu MSAMS Nastavení parametr· je podrobn¥ rozebráno v kapitole 6.
5.2 GAMotifSearch
GaMotifSearch je program na hledání motif· pomocí genetických algoritm·. Na vstup obdrºí N sekvencí ve formátu FASTA a na výstup vydá pozice nejlep-
²ího nalezeného motifu. Vyuºití genetických algoritm· umoº¬uje najít kvalitní motify velice rychle. V následujících sekcích je popsána nejprve reprezentace °e-
²ení pomocí jedinc·, poté vlastní algoritmus, parametry programu a nakonec pouºité genetické operátory.
5.2.1 Reprezentace
Jedinec m·ºe reprezentovat hledaný motif r·znými zp·soby, nap°íklad:
1. Jedinec reprezentuje motif p°ímo (nap°íklad obsahuje textový °et¥zec nebo motif zapsaný v závorkové notaci).
2. Jedinec obsahuje pozici motifu v kaºdé sekvenci.
Nevýhodou první reprezentace je nutnost znovu vyhledávat motif v kaºdé sek- venci p°i ohodnocování ú£elovou funkcí. Proto GAMotifSearch vyuºívá druhou reprezentaci.
Denice. Jedinec v programu GAMotifSearch je N-tice p = (p1, p2, ..., pN), kde pi je pozice motifu vi-té sekvenci a N je po£et sekvencí.
5.2.2 Algoritmus
Program GAMotifSearch je aplikace genetických algoritm· na problém hledání motif·, proto jeho schéma vychází z obecného schématu genetických algoritm·
popsaného v kapitole 2:
Inicializuj a ohodno´ populaci X for i←1 to MaxGeneration do
Y1 ← Vytvo° potomky z X pomocí operátoru globální mutace Y2 ← Vytvo° potomky z X pomocí operátoru lokální mutace Y3 ← Vytvo° potomky z X pomocí operátoru k°íºení
Y4 ← Vytvo° potomky z X pomocí brute-force operátoru Oprav Y1, Y2, Y3
Y ←Y1∪Y2∪Y3∪Y4
Ohodno´ Y ú£elovou funkcí f
X ← Operátorem turnajové selekce vyber novou populaci z X∪Y X ← Odstra¬ duplicitní jedince z X
end
nachází na za£átku první sekvence a na konci druhé sekvence je pro ú£ely dal-
²ího zpracování pomocí MSA nevhodný). Proto je kaºdý nov¥ vytvo°ený jedinec p= (p1, p2, ..., pN) opraven následujícím postupem:
1. Vypo£ítá se konsenzus a jeho st°ední pozice MotifCenter = N1 PN i=1pi. 2. Identikují se sekvence, ve kterých je pozice motifu dále od st°ední pozice
motifu neº(MaxMotifDistance/2), kdeMaxMotifDistance je p°edem zvole- ná nejvy²²í povolená vzdálenost pozic motifu v sekvencích.
3. V t¥chto sekvencích se náhodn¥ vybere nová pozice motifu v intervalu (MotifCenter−MaxMotifDistance/2,MotifCenter +MaxMotifDistance/2). Po oprav¥ jsou noví jedinci ohodnoceni ú£elovou funkcí:
f(x) =
N−1
X
i=1 N
X
j=i+1 l
X
k=1
M(xi+k, xj+k)
N je po£et sekvencí, l je délka motifu,M je pouºitá substitu£ní matice. Navíc je moºné penalizovat jedince reprezentující motif, jehoº pozice jsou vzájemn¥ p°íli² vzdálené za kaºdou dvojici pozic vzdálen¥j²í neº parametr PrefMotifDistance se jedinci sníºí ohodnocení o 0,2. Tento postup umoº¬uje p°esn¥ji omezit rozp¥- tí hledaného motifu (vzdálenost mezi nejvzdálen¥j²ími pozicemi motifu), coº je d·leºité, pokud sekvence obsahují repetice.
Kvalitn¥j²í jedinci mají vy²²í hodnotu ú£elové funkce. Po ohodnocení se z no- vých i p·vodních jedinc· vybere operátorem selekce nová populace. Algoritmus skon£í po provedení MaxGeneration iterací.
5.2.3 Parametry
Parametry programu GAMotifSearch jsou shrnuty v tabulce 2:
Parametr Obor hodnot Popis
MaxGeneration N po£et iterací
PopulationSize {4, ...,∞} po£et jedinc· v populaci
Length N délka hledaného motifu
LocalMutation h0,1i ⊂R pravd¥podobnost pouºití operátoru lokální mutace GlobalMutation h0,1i ⊂R pravd¥podobnost pouºití
operátoru globální mutace Crossover h0,1i ⊂R pravd¥podobnost aplikace
operátoru k°íºení
CrudeSearch h0,1i ⊂R pravd¥podobnost pouºití operátoru brute-force TournamentFactor h0,1i ⊂R
pravd¥podobnost výb¥ru kvalitn¥j²ího jedince v tur- najové selekci
EliteSize {0, ...,PopulationSize} po£et elitních jedinc·
MaxMotifDistance h0,∞)⊂R
maximální vzdálenost po- zic motifu (práh pro opra- vu jedinc· a operátor brute- force)
PrefMotifDistance h0,∞)⊂R preferované rozp¥tí pozic motifu
Matrix °et¥zec soubor se substitu£ní maticí
RunTotal N po£et b¥h· celého algoritmu
Tabulka 2. Parametry programu GAMotifSearch
Zvý²ením po£tu generací nebo velikosti populace je moºné dosáhnout lep²ích vý- sledk· za cenu del²í doby b¥hu algoritmu. Parametry MaxMotifDistance aPrefMotifDistance umoº¬ují omezit rozp¥tí hledaného motifu.
5.2.4 Genetické operátory
Program vyuºívá p¥t genetických operátor· globální a lokální mutaci, k°íºení, operátor brute-force a turnajovou selekci s elitismem, které jsou popsány podrob- n¥ dále.
Globální mutace
V kaºdé iteraci mutuje kaºdý jedinec s pevnou pravd¥podobnostíGlobalMutation. P°i mutaci se p°emístí pozice motifu v náhodn¥ vybrané sekvenci na náhodné mís- to v této sekvenci. V následujícím p°ípad¥ do²lo k mutaci pozice motifu ve druhé sekvenci:
Jedinec p°ed globální mutací: (14, 28, 17, 33, 41) Jedinec po globální mutaci: (14, 11, 17, 33, 41)
Globální mutace umoº¬uje, na rozdíl od k°íºení, najít nové pozice motifu v sek- vencích. Ú£elem globální mutace je zachovávat a zavád¥t diverzitu do populace.
Mutace by m¥la zabránit algoritmu zastavit se v lokálním optimu ú£elové funk- ce. Operátor není nadm¥rn¥ disruptivní, protoºe ke zm¥n¥ jedince dochází pouze v jedné sekvenci.
Lokální mutace
V kaºdé iteraci mutuje kaºdý jedinec s pevnou pravd¥podobnostíLocalMutation, na rozdíl od globální mutace se pozice motifu posune pouze o jedinou bázi. P°í-
K°íºení
Operátor k°íºení provádí jednobodové k°íºení mezi dv¥ma náhodn¥ vybranými rodi£i. Bod k°íºení je rovn¥º vybrán náhodn¥. Výsledkem jsou dva potomci, jak ukazuje následující p°íklad (z rodi£· P1 a P2 byly vytvo°eni potomci O1 a O2, svislá £ára vyzna£uje bod k°íºení):
P1 = (14, 28, 17, | 33, 41) P2 = (18, 24, 16, | 35, 38) O1 = (14, 28, 17, | 35, 38) O2 = (18, 24, 16, | 33, 41)
K°íºení slouºí k rekombinaci °e²ení ze dvou rodi£·. Je nezbytné pro rychlé nalezení kvalitního motifu.
Brute-force
Operátor nejprve zjistí, ve které sekvenci má jedinec nejhor²í motif (kvalita mo- tifu se m¥°í proti konsenzu). Poté se tato sekvence prohledává do vzdálenosti (MaxMotifDistance/2) od st°ední pozice konsenzu se snahou najít pozici odpoví- dající lep²ímu motifu. Nejlep²í nalezená pozice nahradí p·vodní v této sekvenci.
Díky omezení prohledávání není pot°eba nov¥ vytvo°eného jedince opravovat.
Tento operátor podstatn¥ zrychluje nalezení dobrého motifu.
Turnajová selekce s elitismem
Algoritmus pouºívá turnajovou selekci, protoºe je implementa£n¥ jednoduchá, rychlá, nevyºaduje ²kálování ohodnocení jedinc· a dob°e zachovává diverzitu po- pulace. Selekce se stará o výb¥r nové populace podle následujícího algoritmu:
Vloº EliteSize nejlep²ích jedinc· z Y doX for i←EliteSize + 1 to |Y|do
a ←náhodný jedinec z Y
b ← náhodný jedinec z Y,b 6=a if f(a)> f(b) then
if randh0,1) <TournamentFactor then Vloº a doX
elseVloº b doX end
elseif randh0,1) <TournamentFactor then Vloº b doX
elseVloº a doX end
end end
Y je populace po aplikaci ostatních genetických operátor·, X je nová popula- ce, EliteSize je po£et elitních jedinc·, f je ohodnocení jedince ú£elovou funkcí a TournamentFactor je pravd¥podobnost výb¥ru kvalitn¥j²ího jedince. randh0,1)
je funkce vracející náhodné £íslo z intervalu h0,1). Smysl elitismu spo£ívá v za- chování EliteSize nejlep²ích jedinc· do dal²í generace (jinak by se mohlo stát, ºe se nejlep²í jedinec nevybere do ºádného turnaje a tím dojde ke ztrát¥ nejkvalit- n¥j²ího °e²ení). Proto by parametr EliteSize m¥l být vºdy v¥t²í nebo roven 1.
5.3 GASequenceAlignment
GASequenceAlignment je program na °e²ení MSA vyuºívající genetické algoritmy.
Vstupem programu jsou biologické sekvence ve formátu FASTA, výstupem je alig- nment op¥t ve formátu FASTA. Díky pouºití genetických algoritm· dokáºe tento program £asto najít kvalitn¥j²í alignmenty neº ClustalW (dokonce vºdy kvalit- n¥j²í p°i inicializaci pomocí ClustalW). Nevýhodou (oproti programu ClustalW) je zejména vy²²í £asová náro£nost. Program je podrobn¥ popsán v následujících sekcích. Poslední sekce 5.3.7 vysv¥tluje roz²í°ení zavedením kmenového uspo°á- dání.
5.3.1 Reprezentace
Jedinec m·ºe reprezentovat °e²ení MSA r·znými zp·soby, nap°íklad:
1. Jedinec obsahuje celé sekvence v£etn¥ d¥r.
2. Jedinec obsahuje pouze pozice a délky d¥r pro kaºdou sekvenci.
První moºnost je pam¥´ov¥ náro£n¥j²í, ale vhodn¥j²í pro implementaci n¥kterých genetických operátor·. Program GASequenceAlignment pouºívá první reprezen- taci. Kaºdý jedinec je tedy alignment.
5.3.2 Algoritmus
GASequenceAlignment pracuje podle podobného schématu jako GAMotifSearch:
Inicializuj a ohodno´ populaci X for i←1 to MaxGeneration do
Y1 ← Vytvo° potomky z X pomocí operátoru jednobodového k°íºení Y2 ← Vytvo° potomky z X pomocí operátoru vkládání mezer
Y3 ← Vytvo° potomky z X pomocí operátoru posunu blok·
Y4 ← Vytvo° potomky z X pomocí operátoru horizontálního ²t¥pení blok·
Y5 ← Vytvo° potomky z X pomocí operátoru p°esunu mezer Y6 ← Vytvo° potomky z X pomocí operátoru odstran¥ní znaku Y ←Y1 ∪Y2∪Y3∪Y4∪Y5∪Y6
Ohodno´ ú£elovou funkcí
5.3.3 Parametry
Tabulka 3 shrnuje parametry programu GASequenceAlignment:
Parametr Obor hodnot Popis
MaxGeneration N po£et iterací
PopulationSize {4, ...,∞} po£et jedinc· v populaci InitType {RAND,CLUSTALW} volba mezi náhodnou
a ClustalW incializací MaxOset {0, ...,∞} maximální odsazení sekven-
ce p°i inicializaci InitGapFactor h0,1i ⊂R síla inicializace
Crossover h0,1i ⊂R pravd¥podobnost aplikace jednobodového k°íºení GapInsertion h0,1i ⊂R pravd¥podobnost pouºití
operátoru vkládání mezer BlockMove h0,1i ⊂R pravd¥podobnost pouºití
operátoru posunu blok·
BlockSplit h0,1i ⊂R
pravd¥podobnost pouºití operátoru horizontálního
²t¥pení blok·
ShiftMutation h0,1i ⊂R pravd¥podobnost aplikace operátoru p°esun mezer CharDelete h0,1i ⊂R pravd¥podobnost pouºití
operátoru odstran¥ní znaku TournamentFactor h0,1i ⊂R
pravd¥podobnost výb¥ru kvalitn¥j²ího jedince v tur- najové selekci
EliteSize {0, ...,PopulationSize} po£et elitních jedinc·
GapOpenPenalty (−∞,0i ⊂R penalizace jedince za díru GapContPenalty (−∞,0i ⊂R pokuta jedince za mezeru
Matrix °et¥zec soubor se substitu£ní maticí
RunTotal N po£et b¥h· algoritmu
Tabulka 3. Parametry programu GASequenceAlignment
5.3.4 Inicializace jedinc·
Jedince v po£áte£ní populaci je moºné inicializovat dv¥ma zp·soby náhodn¥
nebo pomocí programu ClustalW:
1. Náhodná inicializace nejprve se v kaºdém jedinci vloºí p°ed kaºdou sek- venci náhodný po£et mezer (nejmén¥ 0, nejvý²e MaxOffset). Poté se do kaºdého jedince vloºí dInitGapFactor ·2e d¥r náhodné délky (1 aº 10 me- zer). Díry se vkládají na náhodn¥ vybrané pozice do náhodn¥ vybraných sekvencí.
2. Inicializace z ClustalW na vstupní sekvence je spu²t¥n program ClustalW. Kaºdý jedinec v po£áte£ní populaci vznikne z °e²ení ClustalW, na které se aplikují operátory vkládání mezer, posun blok·, horizontální
²t¥pení blok·, p°esun mezer a odstran¥ní znaku, kaºdý s pravd¥podobností InitGapFactor/5.
Inicializace pomocí programu ClustalW zajistí, ºe kone£né °e²ení bude alespo¬
tak dobré, jaké poskytl ClustalW. Navíc je díky vysoké kvalit¥ jedinc· v po£áte£- ní populaci moºné sníºit velikost populace a po£et iterací a tím program urychlit.
M·ºe se v²ak stát, ºe °e²ení z programu ClustalW bude lokálním optimem za- daného problému a genetický algoritmus z n¥j nedokáºe uniknout. Proto m·ºe být v n¥kterých p°ípadech výhodn¥j²í pouºít náhodnou inicializaci (nap°íklad na jednodu²²ím zadaní, kde pouºití ClustalW není nezbytné).
5.3.5 Ú£elová funkce
Na ohodnocování jedinc· se pouºívá následující funkcef (p°ed ohodnocením je- dince y = a1, ..., aN jsou na konce sekvencí a1, ..., aN p°idány mezery tak, aby byly sekvence zarovnány na stejnou délku):
f(y) =
N−1
X
i=1 N
X
j=i+1
score(ai, aj)
N je po£et sekvencí v jedinci y, score(ai, aj) je skórovací funkce hodnotící za- rovnání mezi sekvencemi ai a aj, která je popsána v podkapitole 2.2. Program vyuºívá anní penalizaci za díry a umoº¬uje zvolit parametry penalizace (pomo- cí parametr· GapOpenPenalty a GapOpenPenalty) a substitu£ní matici (pomocí parametru Matrix).
5.3.6 Genetické operátory
Program vyuºívá sedm genetických operátor· jednobodové k°íºení, vkládá- ní mezer, posun blok·, horizontální ²t¥pení blok·, p°esun mezer, odstran¥ní zna- ku a turnajovou selekci s elitismem. N¥které z operátor· byly inspirovány nebo p°ímo p°ejaty z metody SAGA [2], která je popsána v podkapitole 3.6.
Jednobodové k°íºení
Operátor je p°ejat z metody SAGA (One-point crossover). K°íºení se pouºívá na náhodn¥ vybrané jedince. Na rozdíl od metody SAGA se zachovávají oba potomci, nikoliv pouze ten lep²í.
Vkládání mezer
Posun blok·
Operátor je p°ejat z metody SAGA (Block shuing první zp·sob). P°i aplikaci tohoto operátoru na jedince se p°esune náhodn¥ vybraný blok mezer, vºdy o jednu pozici doleva nebo doprava. Operátor se na kaºdého jedince v populaci pouºije s pravd¥podobností BlockMove.
Horizontální ²t¥pení blok·
Operátor je p°ejat z metody SAGA (Block shuing druhý zp·sob). P°i pouºití operátoru se náhodn¥ vybere blok mezer, horizontáln¥ se rozd¥lí na dv¥ £ásti a jedna náhodn¥ vybraná £ást se p°esune o jednu pozici doleva nebo doprava. Na kaºdého jedince v populaci se operátor aplikuje s pravd¥podobnostíBlockSplit. P°esun mezer
Tento operátor posune náhodn¥ vybranou mezeru v náhodn¥ vybrané sekvenci o jednu pozici doleva nebo doprava, jak ukazuje následující p°íklad:
Sekvence p°ed aplikací operátoru: AAC--GA-TACGT Sekvence po aplikaci operátoru: AAC--GAT-ACGT
Na kaºdého jedince v populaci se aplikuje s pravd¥podobnostíGapShift. Odstran¥ní znaku
Ú£elem operátoru je odstran¥ní náhodn¥ vybraného znaku (nikoliv mezery) z ná- hodn¥ vybrané sekvence. Toho lze dosáhnout vloºením mezery do ostatních sek- vencí na pozici odstra¬ovaného znaku, jak je vid¥t z p°íkladu (odstra¬uje se desátý znak z druhé sekvence):
Jedinec p°ed odstran¥ním znaku:
AAC--GA-TACGT ACA--TACGGACT A-AATACTAACGT AC---TAATACT-
Jedinec po odstran¥ní znaku:
AAC--GA-T-ACGT ACA--TACGGACT A-AATACTA-ACGT AC---TAAT-ACT-
Po pouºití operátoru mají sekvence v jedinci r·znou délku, proto se musí p°ed ohodnocením zarovnat (p°idáním mezer na konec krat²í sekvence). Operátor je aplikován na kaºdého jedince v populaci s pravd¥podobností CharDelete.
Turnajová selekce s elitismem
Turnajová selekce s elitismem funguje zcela identicky jako v programu GAMotif- Search.
5.3.7 Roz²í°ení algoritmu kmenovým uspo°ádáním
MSA je velice obtíºná úloha. Na sloºit¥j²ích zadáních nalezne program GASequen- ceAlignment z°ídka optimální °e²ení. Díky vyuºívání náhodných £ísel m·ºe pro- gram najít r·zná °e²ení jedné úlohy MSA, proto m·ºe být výhodné b¥h gene- tického algoritmu opakovat (v metod¥ GASequenceAlignment se po£et b¥h· °ídí parametremRunTotal).
Výsledky z jednotlivých b¥h· lze dále vyuºít kmenovým uspo°ádáním b¥h· ge- netických algoritm· po provedeníRunTotal b¥h· (pod°ízených kmen·) se získá RunTotal °e²ení zadané úlohy. Poté se spustí záv¥re£ný b¥h genetického algoritmu (hlavní kmen), jehoº po£áte£ní populace obsahujeRunTotal °e²ení z pod°ízených b¥hu a zbytek tvo°í b¥ºn¥ vytvo°ení jedinci (náhodn¥ nebo pomocí ClustalW).
Navíc je moºné do po£áte£ní populace za°adit d°íve nalezená °e²ení (dokonce lze pouºít °e²ení nalezené jiným programem). Hlavní kmen £asto dokáºe najít lep²í
°e²ení pomocí kombinace výsledk· z pod°ízených kmen·. Genetický algoritmus má ve v²ech kmenech v£etn¥ hlavního stejné parametry. Kmenové schéma pro- gramu GASequenceAlignment bylo inspirováno metodou Compounded genetic algorithms [22].
6. Nastavení parametr· metody MSAMS
e²ení MSA metodou MSAMS je °ízeno pomocí velkého mnoºství parametr·. Ty se rozd¥lují na parametry samotného programu MSAMS, parametry programu GAMotifSearch a parametry programu GASequenceAlignment. Tato podkapitola se zabývá jejich nastavením.
Správné nastavení parametr· je obtíºné. Kv·li vzájemné provázanosti para- metr· nelze p°esn¥ zjistit, jak ur£ité nastavení konkrétního parametru ovlivní b¥h programu a kvalitu výsledku. Navíc chování programu závisí na generovaných ná- hodných £íslech, coº zt¥ºuje rozbor vlivu jednotlivých parametr·.
P°esto lze z teoretického návrhu programu, z poznatk· o genetických algorit- mech a z experimentální analýzy vytvo°it pravidla a doporu£ení, která nastavení programu podstatn¥ zjednodu²í. Ty postupn¥ popisuje následující text nejpr- ve parametry samotného programu MSAMS, poté parametry metody GAMotif- Search a nakonec parametry metody GASequenceAlignment. Pokud se p°i b¥hu programu MSAMS vyuºívá i ClustalW, a´ uº p°ímo nebo p°i inicializaci v metod¥
GASequenceAlignment, je moºné dosáhnout lep²ích výsledk· zm¥nou paramet- r· programu ClustalW (n¥které parametry jsou popsány v p°íloze v uºivatelské dokumentaci, v²echny lze najít v dokumentaci programu ClustalW).
P°i hledání vhodných kongurací se lze také inspirovat kongura£ními sou- bory na p°iloºeném CD, které byly pouºity p°i testování programu MSAMS na n¥kterých úlohách z BAliBASE [23] (více v podkapitole 9.2).
6.1 Nastavení parametr· programu MSAMS
Nejprve vybereme mód programu zvolíme Mode = MOTIF, pokud chceme pouze vyhledat motify, Mode = ALIGN, pokud chceme °e²it MSA bez hledá- ní motif· nebo máme motify p°ipravené p°edem, Mode = FULL, kdyº chceme vy°e²it MSA za pomoci hledání motif·.
Pokud se bude vyuºívat hledání motif·, zvolíme po£et hledaných motif· para- metremMSRuns. Aby m¥la metoda GASequenceAlignment dostate£né moºnosti p°i následném zarovnávání sekvencí, doporu£uji omezit po£et hledaných motif·
v závislosti na délce nejkrat²í sekvence do délky 50 znak·MSRuns ≤2, do 100 znak· MSRuns ≤ 3, do 300 znak· MSRuns ≤ 4, nad 300 znak· MSRuns ≤ 6. P°íli² vysoký po£et hledaných motif· m·ºe zp·sobit tyto problémy:
• zvý²í se pravd¥podobnost nalezení p°ek°íºených motif·, takºe n¥které z nich stejn¥ nebudou pouºity,
• metoda GAMotifSeach m·ºe po vy£erpání kvalitních motif· nalézt i nep°íli² kvalitní motify, podle kterých se poté ²patn¥ rozd¥lí úloha a kv·li tomu se nakonec sekvence nepoda°í dob°e zarovnat,
• úloha se roz²t¥pí na p°íli² mnoho £ástí, coº omezí metodu GASequenceA- lignment a výsledný alignment nebude kvalitní.
Pro optimální funkci programu je nutné najít motify p°edem a ru£n¥ zkontrolovat jejich kvalitu a umíst¥ní v sekvencích a poté podle jejich po£tu nastavit hodnotu parametru MSRuns.
Nakonec, pro módyALIGN aFULL, vybereme metodu °e²ení MSA bu¤ ge- netické algoritmy pomocí nastavení Method = GENETIC nebo program ClustalW nastavením Method =CLUSTALW.
6.2 Nastavení parametr· metody GAMotifSearch
ParametryMaxGenerationaPopulationSize by se m¥ly nastavit nejmén¥ na hod- notu 10 (pro b¥ºná zadání je doporu£ené zvolit MaxGeneration v rozmezí 100 a 500 a PopulationSize mezi 20 a 200). Tyto parametry ovliv¬ují dobu b¥hu lineárn¥. Jejich zvý²ením lze £asto najít kvalitn¥j²í motify.
ParametrLength udává délku hledaného motifu, vhodné hodnoty jsou 6 aº 15 pro sekvence DNA a RNA a 3 aº 5 pro proteinové sekvence.
Parametry LocalMutation, GlobalMutation, Crossover a CrudeSearch °ídicí genetické operátory je vhodné zvolit mezi 0,1 a 0,4. Pro kaºdý z t¥chto parametr·
platí, ºe vy²²í hodnota povede k del²í dob¥ hledání motif·. TournamentFactor m·ºe být nastaven nap°íklad na 0,9 nebo 0,95. Vhodná hodnota EliteSize závisí naPopulationSize a m¥la by být nejmén¥ 1 a nejvý²e PopulationSize/10.
Nejlep²í hodnota parametruMaxMotifDistancezávisí na po£tu hledaných mo- tif· a délce a typu sekvencí. M¥la by být vºdy nastavena na hodnotu vy²²í neº 20, pro b¥ºná zadání obsahující sekvence podobné délky lze doporu£it hodnotu 80 pro proteinové sekvence a 200 pro DNA nebo RNA sekvence.PrefMotifDistance doporu£uji nastavit mezi 12 a 23 MaxMotifDistance. Pokud mají sekvence vel- mi rozdílnou délku (nejdel²í sekvence je alespo¬ dvakrát del²í neº nejkrat²í), je vhodné nastavit oba tyto parametry na hodnotu alespo¬ poloviny délky nejdel²í sekvence.
Substitu£ní matici (parametrMatrix) je moºné vyuºít stejnou, jaká bude po- uºita v metod¥ GASequenceAlignment. Nap°íklad pro proteinové sekvence ne- známé podobnosti m·ºeme zvolit matici BLOSUM62 [9].
Po£et b¥h· metody se nastavuje parametrem RunTotal ºádoucí jsou ale- spo¬ 3 b¥hy, aby se omezil vliv náhody v genetických algoritmech, i kdyº pro jednoduchá zadání m·ºe sta£it b¥h jediný.
6.3 Nastavení parametr· metody GASequenceA- lignment
Nejprve se nastaví parametr InitType, protoºe na jeho hodnot¥ m·ºe záviset nastavení jiných parametr·. Volbou varianty CLUSTALW se zaru£í, ºe kvalita
metoda k dispozici.
Vhodné nastavení parametru MaxOffset závisí hlavn¥ na délce sekvencí, p°í- padn¥ také na jejich typu a mí°e podobnosti. V b¥ºných úlohách je moºné zvolit nap°íklad MaxOffset ≥ 10 pro krátké sekvence, MaxOffset ≥ 30 pro sekvence pr·m¥rné délky vy²²í neº 200 bází nebo aminokyselin a MaxOffset ≥ 50 pro sekvence pr·m¥rné délky vy²²í neº 400.
Parametr InitGapFactor je vhodné nastavit na hodnotu 0,5 v p°ípad¥ protei- nových sekvencí a na hodnotu 1 v p°ípad¥ sekvencí DNA nebo RNA. Pokud jsou sekvence dlouhé (nad 500 bází nebo aminokyselin), m·ºe mít zvý²ení hodnoty tohoto parametru kladný efekt (nap°íklad na hodnotu 2).
Parametry Crossover, GapInsertion, BlockMove, BlockSplit, ShiftMutation aCharDelete ur£ují pravd¥podobnosti pouºití jednotlivých genetických operáto- r·. Stejn¥ jako v p°ípad¥ metody GAMotifSearch mají vliv na dobu b¥hu progra- mu, coº je podrobn¥ji analyzováno v podkapitole 9.6. Pro parametry TournamentFactor aEliteSize platí stejná doporu£ení jako v GAMotifSearch.
Parametrem Matrix nastavíme vhodnou substitu£ní matici pro na²e zadání.
Pro proteinové sekvence lze pouºít nap°íklad matice PAM [8] nebo BLOSUM [9].
Pokud nejsou k dispozici informace o zarovnávaných sekvencích, volí se nej£ast¥ji matice BLOSUM62. Poté zvolíme penaliza£ní parametryGapOpen a GapCount. Vhodná nastavení penaliza£ních parametr· pro matice PAM a BLOSUM byla empiricky nalezena v [10]. V p°ípad¥ zarovnávání sekvencí DNA nebo RNA vyu- ºijeme nap°íklad jednotkovou matici.
Po£et b¥h· metody se nastavuje parametrem RunTotal kv·li roz²í°ení ge- netického algorimu pomocí kmenového uspo°ádání by m¥ly prob¥hnout alespo¬
3 b¥hy.
7. Implementace metody MSAMS
Tato kapitola se zabývá implementací programu MSAMS. MSAMS je naprogra- mován v jazyce C++ primárn¥ pro platformu Microsoft Windows. Skládá se z n¥kolika spustitelných soubor· jejich stru£ný p°ehled je v tabulce:
Jméno Funkce
batchrunner.exe Slouºí ke spou²t¥ní dávkových soubor·
clustalw2.exe Program ClustalW °e²í MSA pomocí pro- gresivního algoritmu
gamotifsearch.exe Program GAMotifSearch hledá motify po- mocí genetických algoritm·
gasequencealignment.exe Program GASequenceAlignment °e²í MSA pouºitím genetických algoritm·
msams.exe Program MSAMS °e²í MSA s pomocí hle- dání motif·
score.exe Program na hodnocení alignment·
Tabulka 4. Sou£ásti programu MSAMS
Kaºdý program (krom¥ ClustalW) byl vytvo°en jako samostatný projekt v pro- gramu Microsoft Visual Studio C++. Ve²keré zdrojové kódy jsou k dispozici na p°iloºeném CD v adresá°i source. V podkapitolách 7.1 aº 7.6 jsou programy po- psány podrobn¥ji. Poslední podkapitola 7.7 se zabývá n¥kterými jednoduchými úpravami t¥chto program·. Návod na pouºití programu MSAMS na °e²ení MSA a podrobný popis v²ech kongura£ních soubor· je v uºivatelské dokumentaci v p°íloze.
7.1 Implementace batchrunner.exe
Tento program slouºí k dávkovému zpracování úloh MSA. Program na£te dávku ze souboru v textovém formátu a poté opakovan¥ pouºívá msams.exe na °e²ení kaºdého zadání v této dávce. Program lze spustit p°íkazem:
batchrunner.exe <batch>
Program vyºaduje jeden povinný parametr název dávkového souboru. Jeho formát je popsán v uºivatelské dokumentaci v p°íloze.
clustalw2.exe [parametry]
Program lze nastavit pomocí mnoha parametr· (n¥které jsou popsány v p°ílo- ze v uºivatelské dokumentaci programu MSAMS). Pokud nejsou zadány ºádné parametry, program se spustí v interaktivním konzolovém reºimu.
7.3 Implementace GAMotifSearch
Program GAMotifSearch se pouºívá na vyhledávání motif· pomocí genetických algoritm·. Je moºné ho spustit samostatn¥ pomocí p°íkazu:
gamotifsearch.exe <motifsearch.cfg> [data.fasta] [seeds.txt]
Prvním povinným parametrem je název kongura£ního souboru (jeho formát a pouºitelné parametry jsou popsány v p°íloze v uºivatelské dokumentaci). Druhý parametr je volitelný a obsahuje název souboru se sekvencemi v textovém nebo FASTA formátu, ve kterých bude probíhat hledání motifu. T°etí parametr je ta- ké nepovinný a obsahuje název soubor se vstupy pro generátor pseudonáhodných
£ísel.
Program nejprve na£te parametry, sekvence a vstupy generátoru pseudoná- hodných £ísel. Poté vytvo°í ú£elovou funkci jako objekt t°ídy MSFitness. Pak se postupn¥ spou²tí b¥hy genetického algoritmu. Genetický algoritmus °e²ící hledání motif· je implementován ve t°íd¥ MotifSearch. Její nejd·leºit¥j²í metody jsou popsány v následující tabulce:
Metoda Funkce
MotifSearch(...)
konstruktor t°ídy s mnoha parametry, který se stará zejména o inicializaci po£áte£ní popula- ce
void execute() spou²tí vlastní genetický algoritmus opako- van¥ provádí implementované genetické operá- tory dokud není spl¬eno ukon£ovací kritérium double evalIndividual
(size_t i) ohodnotí i-tého jedince populace ú£elovou funkcí a vrátí jeho ohodnocení
void globalMutation() aplikuje operátor globální mutace na celou po- pulaci
void localMutation() aplikuje operátor lokální mutace na celou populaci
void bruteSearch() provede operátor brute-force na celou popula- ci
void simpleCrossover() provede jednobodové k°íºení v celé populaci tournamentSelection()void implementuje turnajovou selekci s elitismem
Tabulka 5. D·leºité metody t°ídy MotifSearch
