af

Dette speciale omhandler algoritmer til at finde eksakte motiver i DNA-sekvenser med fokus p̊a praktisk hastighed. Algoritmerne bliver testet i praksis med for-skellige længder af DNA-sekvenser og forskellige længder af motiver, hvor input er dele af det menneskelige DNA. Algoritmerne bliver analyseret p̊a hukommel-sesforbrug, reel brugt tid, antal CPU-cykler til beregning og antal CPU-cykler til at vente p̊a cache miss. Der bliver i specialet eksperimenteret med algoritmerne/datastrukturerne: McCreights Suffixtræ, K-Trie, Hash-Splay, Radix Sort, Deep-Shallow (Suffixar-ray), Bucket-Copy og en filtrerings teknik, kaldet Crude Filter, til preprocesse-ring. Hash-Splay, Bucket-Copy og Crude Filter er algoritmer, som er designet i forbindelse med dette speciale, mens de andre algoritmer er blevet udvidet med optimeringer og motiv-identifikations- og optællings-metoder. Der opn̊as, for de enkelte algoritmer, en viden om ikke blot den reelle tid, men ogs̊a hvorfor algoritmen bruger denne tid. Denne viden kommer fra analy-sen af hvad CPU-cyklerne i algoritmerne bliver anvendt til. Den fundne viden benyttes til at designe nye algoritmer og der gives anbefalinger til design af cache-optimale algoritmer. Endelig bliver de enkelte algoritmer evalueret mod hinanden og der findes de i praksis hurtigste algoritmer. Bucket-Copy er hurtigst til fuld identifikation, gruppering og optælling af motiver, mens Crude Filter metoden er hurtigst, n̊ar der kun skal findes overrepræsenterede motiver. v vi This thesis is about algorithms for finding exact motives in DNA sequences, with focus on speed in practice. The algorithms are tested in practice, with DNA sequences of different length, and searching for motives of different lengths, on input from the human DNA. The algorithms are analyzed with respect to memory usage, real time used, number of CPU cycles used for calculation and number of CPU cycles used for waiting for cache misses. In this thesis we perform experiments with the algorithms and data structu