| Popis: |
U bioinformatici, poravnanje nizova (ili sekvenci) je način raspoređivanja primarnih bioloških nizova DNA, RNA ili proteina kako bi se odredile regije sličnosti koje mogu biti posljedica funkcionalnih, strukturnih ili evolucijskih odnosa između nizova. Ako dva niza u poravnanju dijele zajedničkog pretka, nepodudarnosti se mogu tumačiti kao točkaste mutacije, a praznine kao mutacije umetanja ili brisanja uvedene u jednu ili obje loze u vremenu kad su se razišle. U poravnavanju proteinskih bioloških nizova, stupanj sličnosti između aminokiselina koje zauzimaju određenu poziciju u nizu može se interpretirati kao gruba mjera koliko je određena regija ili motiv biološkog niza očuvan medu lozama. Odsutnost supstitucija, ili prisutnost samo vrlo konzervativnih supstitucija (supstitucija aminokiselina čiji bočni lanci imaju slična biokemijska svojstva) u određenoj regiji biološkog niza, sugeriraju da ova regija ima strukturnu ili funkcionalnu važnost. Iako su nukleotidne baze DNK i RNK sličnije jedna drugoj nego aminokiselinama, očuvanje uparivanja baza može ukazivati na sličnu funkcionalnu ili strukturnu ulogu. Vrlo kratki ili vrlo slični biološki nizovi mogu se poravnati ručno; međutim, najzanimljiviji problemi zahtijevaju poravnavanja dugih, vrlo varijabilnih ili iznimno brojnih bioloških nizova koji se ne mogu uskladiti isključivo ljudskim naporom. Računalni pristupi poravnavanju nizova općenito spadaju u dvije kategorije: globalna poravnanja i lokalna poravnanja. Određivanje globalnog poravnanja oblik je globalne optimizacije koja vodi poravnanje tako da se proteže cijelom dužinom svih nizova upita. Suprotno tome, lokalna poravnanja određuju regije sličnosti unutar dugih bioloških nizova koji se općenito jako razlikuju. Lokalna poravnanja često su poželjnija, ali ih može biti teže izračunati zbog dodatnog izazova identificiranja regija sličnosti. Cilj ovog diplomskog rada je opisati, analizirati i primijeniti računalne algoritme za problem poravnanja bioloških nizova, uključujući spore, ali formalno optimizirajuće metode poput dinamičkog programiranja i učinkovite heurističke algoritme za pretraživanje baze podataka. Praktični dio rada uključuje istraživanje sličnosti između pojedinih varijanti viralnih proteina, npr. protein šiljka (engl. spike protein) u varijantama SARS-CoV-2 virusa. In bioinformatics, array alignment (or sequences) is a way of arranging primary DNA, RNA, or protein sequences to determine similarity regions that may be the result of functional, structural, or evolutionary relationships between sequences. If two strings in the alignment share a common ancestor, the mismatches can be interpreted as point mutations, and the gaps as mutations of insertion or erasure are introduced into one or both lineages at the time they diverged. In the alignment of protein sequences, the degree of similarity between amino acids that occupy a particular position in a sequence can be interpreted as a rough measure of how much a particular region or sequence motif is preserved among the lineages. The absence of substitutions, or the presence of only very conservative substitutions (amino acid substitution whose lateral chains have similar biochemical properties) in a particular sequence region, suggests that this region has structural or functional significance. Although nucleotide bases of DNA and RNA are more similar to each other than amino acids, preserving base pairing may indicate a similar functional or structural role. Very short or very similar sequences can be aligned by hand; however, the most interesting problems require alignments of long, highly variable, or extremely numerous sequences that cannot be reconciled solely by human effort. Computer methods to sequences alignment generally fall into two categories: global alignments and local alignments. Determining global alignment is a form of global optimization that guides alignment so that it extends along the entire length of all query strings. In contrast, local alignments determine similarity regions within long sequences that generally vary widely. Local settlements are often preferable but can be more difficult to calculate due to the additional challenge of identifying similar regions. The goal of this thesis is to describe, analyze, and apply computer algorithms for the problem of sequence alignment, including slow but formally optimizing methods such as dynamic programming and effective heuristic database search algorithms. The practical part of the paper includes research on the similarities between individual variants of viral proteins, eg. spike protein in variants of SARS-CoV-2 viruses. |
