Approximate Algorithm for Computing Alignment Between Two Long Sequences

Globalno poravnanje genoma važan je problem genomike. Zbog duljine genoma, računanje optimalnog puta poravnanja točnim algoritmima dinamičkog programiranja računalno je neizvedivo. Cilj ovog rada predstavljanje je i implementacija heurističkog algoritma poravnanja temeljenog na tehnikama traženja predstavnika i procjene Jaccardovog koeficijenta sličnosti skiciranjem. U poglavlju 2 dan je popis pretpostavki neophodnih za rad algoritma te popis pojmova za pomoć pri njegovom razumijevanju. Poglavlje 3 iznosi formalnu definiciju problema, a konkretan algoritam razvijen za njegovo rješavanje opisan je poglavljem 4. Implementacijski specifični detalji nevažni za opis algoritma na visokoj razini navedeni su u poglavlju \5. Rezultati i učinkovitost implementiranog algoritma istraženi su u poglavlju 6. Konačno, poglavlje 7 ukratko izdvaja najbitnije ideje rada.Global sequence alignment is an important problem in the field of genomics. At the whole genome scale, computing the optimal alignment path by using an exact dynamic programming algorithm is computationally impossible. This paper looks to present and implement a heuristic alignment algorithm which relies on computing sequence minimizers and sketch-based estimations of the Jaccard index. The assumptions and preliminaries necessary to understand the algorithm are given by chapter 2. Chapter 3 formally defines the studied problem, while chapter 4 presents and explains the proposed solution. Implementation details not directly connected to the algorithm itself are listed in chapter 5. Performance and results yielded by the implementation are explored in chapter 6. Chapter 7 provides a quick overview of the main ideas presented throughout the paper