Στοίχιση Αλληλουχιών με χρήση Δομών Ευρετηρίων για Χρονοσειρές

Sequence Alignment using Index Structures for Time Series (english)

  1. MSc thesis
  2. ΚΩΝΣΤΑΝΤΙΝΟΣ ΤΣΕΚΑΣ
  3. Βιοπληροφορική και Νευροπληροφορική (ΒΝΠ)
  4. 19 February 2023
  5. Ελληνικά
  6. 79
  7. Κονδυλάκης, Χαρίδημος
  8. Στοίχιση Αλληλουχιών, ADS-Full, Blast, DNA, Σύγκριση αλγορίθμων, Βάση δεδομένων ανθρώπινου γονιδιώματος, Human Genome Reference Sequence, 1000 Genome Project
  9. ΒΝΠ55
  10. 1
  11. 26
    • Όλοι οι ζωντανοί οργανισμοί χαρακτηρίζονται από την ικανότητα να αναπαράγονται και να εξελίσσονται. Το γονιδίωμα ενός οργανισμού ορίζεται ως η συλλογή DNA μέσα σε αυτόν τον οργανισμό, συμπεριλαμβανομένου του συνόλου των γονιδίων που κωδικοποιούν πρωτεΐνες. Αφού βρεθεί ένα νέο γονίδιο, οι βιολόγοι συνήθως δεν γνωρίζουν για τη λειτουργία του. Μια κοινή προσέγγιση για την εξαγωγή συμπερασμάτων της λειτουργίας ενός γονιδίου με νέα αλληλουχία είναι η εύρεση ομοιοτήτων με γονίδια γνωστής λειτουργίας. Από το 1995 που αναλύθηκε για πρώτη φορά η αλληλουχία του πλήρους γονιδιώματος του πρώτου οργανισμού – ενός βακτηρίου, μέσα σε λίγα χρόνια από τότε, τα γονιδιώματα χιλιάδων οργανισμών έχουν ολοκληρωθεί σε αλληλουχία, εγκαινιάζοντας μια νέα εποχή απόκτησης βιολογικών δεδομένων και προσβασιμότητας πληροφοριών. Οι αλληλουχίες αυτές των γονιδιωμάτων αποθηκεύονται σε διαθέσιμες στο κοινό τράπεζες δεδομένων που περιέχουν πλέον δισεκατομμύρια νουκλεοτίδια δεδομένων αλληλουχίας DNA που συλλέγονται από περισσότερους από 260.000 διαφορετικούς οργανισμούς. Συγκεκριμένα, βρισκόμαστε σε μια εποχή που ο αριθμός των ζευγών βάσεων DNA για τον άνθρωπο συγκεκριμένα που έχουν κατατεθεί στα δημόσια αποθετήρια του κόσμου έχει φτάσει τα δεκάδες δισεκατομμύρια. Ωστόσο δεν αρκεί απλώς να έχουμε μεγάλες βάσεις γονιδιωμάτων αν δεν μπορούμε να τις χρησιμοποιήσουμε και απαντήσουμε διάφορα ερωτήματα. Ένα από τα πιο βασικά ερωτήματα σχετικά με ένα γονίδιο ή πρωτεΐνη είναι αν σχετίζεται με οποιοδήποτε άλλο γονίδιο ή πρωτεΐνη. Η συσχέτιση δύο πρωτεϊνών σε επίπεδο αλληλουχίας υποδηλώνει ότι είναι ομόλογες. Η συσχέτιση υποδηλώνει επίσης ότι μπορεί να έχουν κοινές λειτουργίες. Με την ανάλυση πολλών αλληλουχιών DNA και πρωτεϊνών, είναι δυνατός ο εντοπισμός περιοχών ή μοτίβων που μοιράζονται μεταξύ μιας ομάδας μορίων. Αυτές οι αναλύσεις της συγγένειας πρωτεϊνών και γονιδίων επιτυγχάνονται με ευθυγράμμιση αλληλουχιών. Καθώς ολοκληρώνουμε την αλληλουχία των γονιδιωμάτων πολλών οργανισμών, το έργο της εύρεσης του τρόπου με τον οποίο οι πρωτεΐνες σχετίζονται μέσα σε έναν οργανισμό και μεταξύ των οργανισμών γίνεται όλο και πιο θεμελιώδες για την κατανόηση της ζωής μας. Για τον λόγο αυτό στην παρούσα εργασία συγκρίνουμε έναν αλγόριθμο στοίχισης αλληλουχιών και έναν αλγόριθμο δεικτοδότησης και αναζήτησης σε χρονοσειρές, εξατάζοντας κατά πόσο αλγόριθμου αναζήτησης χρονοσειρών μπορούν να βοηθήσουν στην ταχύτερη και ποιοτικότερη εύρεση στοιχίσεων στο γονιδίωμα. Ο πρώτος αλγόριθμος αιχμής είναι ο Blast και ο δεύτερος ο ADS-Full. Χρησιμοποιώντας της ίδιες βάσεις δεδομένων ανθρώπινου γονιδιώματος και τον ίδιο αριθμό αλληλουχιών ερωτημάτων και έπειτα εκτελώντας και τους δύο στο ίδιο υπολογιστικό σύστημα είμαστε σε θέση να τους συγκρίνουμε μέσω των αποτελεσμάτων στοίχισης. Έπειτα, από τα εξαγόμενα αποτελέσματα θα μπορέσουμε να αναγνωρίσουμε τα δυνατά και αδύνατα σημεία του κάθε αλγορίθμου και να τους αξιολογήσουμε.
    • All living organisms are characterized by the ability to reproduce and evolve. The genome of an organism is defined as the collection of DNA within that organism, including the set of genes that encode proteins. After a new gene is found, biologists usually have no idea about its functioning. A common approach to drawing conclusions about the function of a gene with a new sequence is to find similarities with genes of known function. Since 1995, when the sequence of the complete genome of the first organism – a bacterium – was first analyzed, within a few years of then, the genomes of thousands of organisms have been sequenced, ushering in a new era of biodata acquisition and information accessibility. These genome sequences are stored in publicly available databases that now contain billions of DNA sequence nucleotides collected from more than 260,000 different organisms. We are at a time when the number of DNA base pairs for humans, are deposited in the public repositories of the world has reached tens of billions. However, it is not enough just to have large genome bases if we cannot use them and answer various questions. One of the most basic questions about a gene or protein is whether it is related to any other gene or protein. The correlation of two proteins at the sequence level suggests that they are homologous. The correlation also suggests that they may have common functions. By analyzing multiple DNA and protein sequences, it is possible to identify regions or patterns that are shared between a group of molecules. These analyses of protein and gene affinity are achieved by sequence alignment. As we complete the genome sequence of many organisms, the task of finding out how proteins relate within an organism and between organisms becomes increasingly fundamental to understanding our lives. For this reason, in this thesis we compare a sequence alignment algorithm and an algorithm for indexing and searching in time series. The first cutting-edge algorithm is Blast and the second is ADS-Full. Using the same human genome databases and the same number of query sequences and then running both on the same computer system we are able to compare them through the alignment results. Then, from the extracted results we will be able to identify the strengths and weaknesses of each algorithm and evaluate them.
  13. Hellenic Open University
  14. Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές