Το πρόβλημα της ευθυγράμμισης βιολογικών ακολουθιών, δηλαδή πρωτεϊνών και γονιδιακών ακολουθιών, είναι από τα πιο απαιτητικά στην επίλυση και ταυτόχρονα πιο εφαρμόσιμα προβλήματα που σχετίζονται με την επιστήμη της βιοπληροφορικής. Από την ευθυγράμμιση βιολογικών ακολουθιών προκύπτει ένας σημαντικός όγκος πληροφορίας που δίνει απαντήσεις σε εξελικτικά ερωτήματα αλλά, κυρίως, βρίσκει εφαρμογή σε πληθώρα τομέων, όπως η διάγνωση και η θεραπεία ασθενειών. Πρόκειται για ένα θέμα που τράβηξε την προσοχή της παγκόσμιας κοινότητας της πληροφορικής μόλις στο δεύτερο μισό του περασμένου αιώνα, επομένως είναι ένα πεδίο με αρκετό χώρο για έρευνα. Στην παρούσα εργασία, αφού δοθεί το απαραίτητο βιολογικό υπόβαθρο, παρουσιάζονται αρχικά οι βασικότεροι αλγόριθμοι που έχουν παρουσιαστεί μέχρι τώρα ως προτάσεις για την εκτέλεση ευθυγραμμίσεων, εξηγούνται οι βασικές δομικές και λειτουργικές διαφορές τους και δίνεται μια πρώτη εκτίμηση της αποτελεσματικότητάς τους, όπως αυτή αντλείται από τη βιβλιογραφία. Στη συνέχεια, το ενδιαφέρον επικεντρώνεται στον αλγόριθμο τοπικής ευθυγράμμισης BLAST. Αναλύεται η λειτουργία του βήμα προς βήμα, παρουσιάζονται οι κυριότερες εκδόσεις του, οι είσοδοι και οι έξοδοί του καθώς και το μαθηματικό υπόβαθρο στο οποίο βασίζεται η υλοποίησή του. Στόχος του πειραματικού τμήματος της εργασίας είναι να εξετάσει κατά πόσο ο BLAST επιτυγχάνει να ταυτοποιήσει, και με τι σφάλμα, μια μεταλλαγμένη ακολουθία, τόσο ως προς το γονίδιο από το οποίο προέρχεται όσο και ως προς το είδος της και τις πιθανές της συνέπειες στον οργανισμό στον οποίο εκφράζεται. Με βάση το γονίδιο BRCA1 του Homo Sapiens, παράγεται μια σειρά μεταλλάξεων, οι οποίες μεταφράζονται. Το σύνολο των παραγομένων βιολογικών ακολουθιών, νουκλεοτιδιακών και αμινοξεϊκών, τίθεται προς αναζήτηση με χρήση του BLAST σε κατάλληλες βάσεις δεδομένων, προκειμένου να ελεγχθεί η ευαισθησία του σε μεταλλάξεις διαφορετικού τύπου και έκτασης. Αποδεικνύεται ότι παρότι ο BLAST επιτυγχάνει με πολύ μικρό σφάλμα την ταυτοποίηση του γονιδίου, ακόμα και σε περιπτώσεις έντονης μετάλλαξης της αρχικής ακολουθίας, ωστόσο η κατανομή των αποτελεσμάτων είναι πολύ πιο ασαφής ως προς την ταυτοποίηση του είδους της μετάλλαξης. / The goal of the present thesis is the examination of the sensitivity of the local alignment algorithm BLAST, on a set of mutated biological sequences. The algorithm's sensitivity is to be measured with regard to three basic criteria: - identification of the relation to the original gene - identification of the mutation type - prediction of possible influence of the organism in question In the first, theoretical part of the thesis, a general biological background is offered, followed by a sufficient presentation on both the history and the latest achievements in the field of sequence alignment. The main topic introduced is the structure and functionality of BLAST, together with its principal editions, its inputs and outputs and the mathematical foundation standing below it. In the experimental part of the thesis, the BRCA1 gene is picked out of the Homo Sapiens Genome; its sequence suffers a number of mutations of different type and extent. Each produced mutation is translated into the corresponding protein. The entire set of biological sequences produced is going through a BLAST Search to test the sensitivity of the algorithm according to the mutation under examination. Analyzing the results, it is safe to claim that BLAST succeeds to recognize the gene from which the mutated sequences are produced, including extremely low error in the process. On the other hand, the identification of the mutation type is certainly of significantly lower sensitivity. Thus the main proposal extracted is the implementation of a patterns recognition system, which will integrate artificial intelligence methods to connect patterns encountered within the input sequence, with diseases reported in the appropriate documentation.

[pt] Nos últimos anos surgiram novas tecnologias de sequenciamento de DNA conhecidas como NGS - Next-Generation Sequencing. Estas são responsáveis por tornar o processo de sequenciamento mais rápido e menos custoso, mas também trazem como resultado fragmentos de DNA muito pequenos, conhecidos como reads. A montagem do genoma a partir destes fragmentos é considerada um problema complexo devido à sua natureza combinatória e ao grande volume de reads produzidos. De maneira geral, os biólogos e bioinformatas escolhem o programa montador de sequências sem levar em consideração informações da eficiência computacional ou da qualidade biológica do resultado. Esta pesquisa tem como objetivo auxiliar aos usuários biólogos a avaliar a qualidade dos resultados da montagem. Primeiramente, foi projetada e desenvolvida uma metodologia para obter informações dos genes presentes na montagem, listando os genes que podem ser identificados, aqueles que têm o tamanho correto e a sequência de pares de bases correta. Em segundo lugar, foram realizados testes experimentais exaustivos envolvendo cinco dos principais montadores de genoma conhecidos na literatura os quais são baseados no uso de grafos de Bruijn e oito genomas de bactérias. Foram feitas comparações estatísticas do resultado usando as ferramentas QUAST e REAPR. Também foram obtidas informações qualitativas dos genes usando o algoritmo proposto e algumas métricas de eficiência. Em função dos resultados coletados, é feita uma análise comparativa que permite aos usuários conhecer melhor o comportamento das ferramentas consideradas nos testes. Por fim, foi desenvolvida uma ferramenta que recebe diferentes resultados de montagens de um mesmo genoma e produz um relatório qualitativo e quantitativo para o usuário interpretar os resultados de maneira integrada. / [en] New DNA sequencing technologies, known as NGS - Next-Generation Sequencing, are responsible for making the sequencing process more efficient. However, they generate a result with very small DNA fragments, known as reads. We consider the genome assembly from these fragments a complex problem due to its combinatorial nature and the large volume of reads produced. In general, biologists and bioinformatics experts choose the sequence assembler program with no regard to the computational efficiency or even the quality of the biological result information. This research aims to assist users in the interpretation of assembly results, including effectiveness and efficiency. In addition, this may sometimes increase the quality of the results obtained. Firstly, we propose an algorithm to obtain information about the genes present in the result assembly. We enumerate the identified genes, those that have the correct size and the correct base pair sequence. Next, exhaustive experimental tests involving five of the main genome assemblers in the literature which are based on the use of graphs of Bruijn and eight bacterial genomes data set were ran. We have performed statistical comparisons of results using QUAST and REAPR tools. We have also obtained qualitative information for the genes using the proposed algorithm and some computational efficiency metrics. Based on the collected results, we present a comparative analysis that allows users to understand further the behavior of the tools considered in the tests. Finally, we propose a tool that receives different assemblies of the same genome and produces a qualitative and quantitative report for the user, enabling the interpretation of the results in an integrated way.

This master thesis describes theoretical knowledge of biological sequences, principles entropy rate estimates and possibilities of compression of DNA sequences using the substitution methods. Thesis includes practical application of the compression algorithm and practical estimation of entropy.

Αντικείμενο της παρούσας διδακτορικής διατριβής είναι η μελέτη και η σχεδίαση αποδοτικών αλγορίθμων για τη διαχείριση και ανάλυση ακολουθιών βιολογικών δεδομένων. Οι αλγόριθμοι που θα περιγράψουμε εφαρμόζονται σε προβλήματα Βιοπληροφορικής, όπως η αναγνώριση γνωστών ή άγνωστων μοτίβων του DNA και RNA, που εμπλέκονται σε ποικίλες βιολογικές διεργασίες καθώς και η ανακάλυψη περιοδικοτήτων. Ειδικότερα οι αλγόριθμοι που θα παρουσιάσουμε χρησιμοποιούνται για την ανάλυση Βιολογικών Ακολουθιών με “αδιάφορους χαρακτήρες” και Βιολογικών Ακολουθιών με Βάρη. Οι Βιολογικές Ακολουθίες με “αδιάφορους χαρακτήρες” αναπαριστούν συνήθως οικογένειες πρωτεϊνών ενώ οι Βιολογικές Ακολουθίες με βάρη αναπαριστούν συναρμολογούμένες ακολουθίες γονιδιωμάτων που έχουν πρόσφατα αλληλουχηθεί. Στις Βιολογικές Ακολουθίες με αδιάφορους χαρακτήρες παρουσιάζουμε δυο αποδοτικούς αλγορίθμους γραμμικού χρόνου για τον υπολογισμό της περιόδου και τον υπολογισμό του καλύμματος. Ο δεύτερος αλγόριθμος εφαρμόζεται και σε κυκλικά (circular DNAs). Στις Βιολογικές Ακολουθίες με βάρη παρουσιάζουμε δυο αλγορίθμους για τον υπολογισμό των βασικών περιοδικοτήτων: της περιόδου και του καλύμματος ενώ επιλύουμε και το πρόβλημα της εύρεσης προτύπου. Η ανάγκη για αποδοτική διαχείριση βιολογικών ακολουθιών με βάρη μας ώθησε να εισάγουμε μια νέα αποδοτική δομή η οποία επιλύει αποδοτικά τα 2 προηγούμενα προβλήματα. Η δομή αυτή ονομάζεται Δέντρο Επιθεμάτων με Βάρη. Χρησιμοποιώντας το Δέντρο Επιθεμάτων με Βάρη επιλύουμε διάφορες παραλλαγές του προβλήματος εξαγωγής μοτίβων από Βιολογικές Ακολουθίες με Βάρη. Τέλος αποφασίσαμε να μελετήσουμε τη χρήση των Γενετικών Αλγορίθμων και του Εξελικτικού Προγραμματισμού στην ανάλυση ακολουθιών βιολογικών δεδομένων. Αποτέλεσμα αυτής της μελέτης είναι η περιγραφή ενός γενετικού αλγορίθμου που υπολογίζει τις επαναλήψεις σε μια βιολογική ακολουθία. / The object of this doctoral thesis is the study and the design of efficient algorithms for the analysis of sequences of biological data. The algorithms that we describe have application on Bioinformatics problems, such as the recognition of known or unknown patterns in DNA and RNA that are involved in various biological activities, as well as the discovery of periodicities. More specifically the algorithms that we present are used for the analysis of Biological Sequences with “don't care characters”' and Weighted Biological Sequences. Biological Sequences with “don't care characters”, usually represent protein families while Weighted Biological Sequences represent assembled sequences of genomes that they have been recently sequenced. In Biological Sequences with “don't care characters”' we present two efficient algorithms of linear time for the computation of the period and the cover. The second algorithm is also applied in circular DNAs . In Weighted Biological Sequences we present two algorithms for the computation of basic periodicities: the period and the cover, while we also solve the problem of pattern matching. The need for efficient management of biological sequences with weights prompted us to introduce a new efficient data structure which solves efficiently the two precedents problems. This structure is named Weighted Suffix Tree. Using the Weighted Suffix Tree we solve various instances of the motif discovery problem in Biological Weighted Sequences. Finally we decided to study the use of Genetic Algorithms and Evolutionary Programming in the analysis of biological sequences. The result of this study is the description of a genetic algorithm that computes the repetitions in a biological sequence.