Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Επιτάχυνση μέσω υλικού (hardware) αλγορίθμων για συστοιχία γονιδιώματος

Galanos Georgios

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/273DCAAF-7A83-47BE-A322-77F827DDC8AD-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.90191-
Γλώσσαen-
Μέγεθος77 pagesel
Μέγεθος1,6 megabytesen
ΤίτλοςHardware acceleration of genome assembly algorithmsen
ΤίτλοςΕπιτάχυνση μέσω υλικού (hardware) αλγορίθμων για συστοιχία γονιδιώματος el
ΔημιουργόςGalanos Georgiosen
ΔημιουργόςΓαλανος Γεωργιοςel
Συντελεστής [Επιβλέπων Καθηγητής]Dollas Apostolosen
Συντελεστής [Επιβλέπων Καθηγητής]Δολλας Αποστολοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Zervakis Michailen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Ζερβακης Μιχαηλel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Κωτούλας Γεώργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Kotoulas Georgiosen
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electrical and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
ΠεριγραφήΔιπλωματική εργασία Γαλανού Γεωργίου Σχολής ΗΜΜΥ Πολ. Κρήτης με σκοπό την λήψη του πτυχίου Ηλεκτρολόγου Μηχανικού και Μηχανικού Υπολογιστών.el
ΠερίληψηGenome assembly is a field of bioinformatics that refers to the process of taking small fragments of genetic material and putting them back together by different methods in order to reconstruct the original sequence from which the DNA originated. As the DNA input datasets has numerous data size and in most cases has a very large amount of data, it is important to implement functions and algorithms in order to speedup these processes and gain significant time and space reductions in complexity. The Reads Matching Filter (RMF), which i implemented and present in this diploma thesis, is a kind of these processes and it has a preprocessing role in the whole genome assembly process. The RMF takes the input dataset which contains the genetic material separated in reads, one per line and implement a matching process between each other in order to find unused redundancy. As the matching process executed successfully, the unused redundancy thrown out of the dataset and remain the output reads from the algorithm which they called intermediate contigs. The final output file that contains these intermediate contigs has less reads in number and bigger or equal than the input dataset’s reads in length but without the unused redundancy and in this way the overall dataset size gets smaller. Exploited this result, the genome assembly process take a smaller dataset as input and as a result gain a time benefit in execution procedure. The above algorithm implemented both in a software only and in a softwarehardware design in Field Programmable Gate Array (FPGA) in order to gain an acceleration in execution time. The outputs of my design and the original input dataset are given as input in Velvet genome assembler which based on the manipulation of de Bruijn graphs, via the removal of errors and the simplication of repeated regions, in order to process the assembly and give the output sequences. The overall design included the genome assembly processing gained a speedup of the order of 2x-6x ratio, with good quality in the results between the two methods.en
ΠερίληψηΗ συστοιχία γονιδιωμάτων (Genome Assembly) είναι ένα πεδίο της βιοπληροφορικής που αναφέρεται στη διαδικασία λήψης μικρών μερών γενετικού υλικού και επανασύνδεσής τους, με διαφορετικές μεθόδους, προκειμένου να αναδημιουργηθεί η αρχική αλληλουχία από την οποία προήλθε το DNA. Δεδομένου ότι τα σύνολα δεδομένων εισόδου των DNA έχουν πολυάριθμο μέγεθος και στις περισσότερες περιπτώσεις έχει πολύ μεγάλο όγκο δεδομένων, είναι σημαντικό να εφαρμοστούν λειτουργίες και αλγόριθμοι προκειμένου να επιταχυνθούν αυτές οι διαδικασίες και να επιτευχθούν σημαντικές μειώσεις χρόνου και χώρου όσον αφορά την πολυπλοκότητά τους. Το φίλτρο ανάγνωσης (Read Matching Filter - RMF), το οποίο υλοποίησα και παρουσιάζω σε αυτή τη διπλωματική εργασία, είναι ένα είδος αυτών των διαδικασιών και έχει τον ρόλο της προεπεξεργασίας (φιλτράρισμα) των δεδομένων εισόδου σε ολόκληρη τη διαδικασία συστοιχίας γονιδιώματος. Το RMF παίρνει το σύνολο δεδομένων εισόδου που περιέχει το γενετικό υλικό διαχωρισμένο σε μέρη που ονομάζονται reads, ένα ανά γραμμή και εφαρμόζει μια διαδικασία αντιστοίχισης μεταξύ τους προκειμένου να βρεθεί αχρησιμοποίητος πλεονασμός. Όταν η διαδικασία αντιστοίχισης εκτελεσθεί επιτυχώς, ο αχρησιμοποίητος πλεονασμός εξαλείφεται από το σύνολο δεδομένων και παραμένει στην έξοδο της σχεδίασης τα εναπομείναντα reads τα οποία ονομάζονται ενδιάμεσα contigs. Το τελικό αρχείο εξόδου που περιέχει αυτά τα ενδιάμεσα contigs έχει λιγότερα reads σε αριθμό και μεγαλύτερα ή ίσα reads σε μήκος σε σχέση με αυτά του συνόλου δεδομένων εισόδου, αλλά χωρίς τον αχρησιμοποίητο πλεονασμό και με αυτόν τον τρόπο το συνολικό μέγεθος του συνόλου δεδομένων γίνεται μικρότερο. Αξιοποιώντας αυτό το αποτέλεσμα, η διαδικασία συναρμολόγησης γονιδιώματος λαμβάνει ένα μικρότερο σύνολο δεδομένων ως είσοδο και ως αποτέλεσμα κερδίζει ένα χρονικό όφελος στην διαδικασία εκτέλεσης. Ο παραπάνω αλγόριθμος εφαρμόστηκε τόσο σε λογισμικό όσο και σε σχεδιασμό λογισμικού-υλικού σε Field Programmable Gate Array (FPGA) προκειμένου να επιταχυνθεί ο χρόνος εκτέλεσης. Οι έξοδοι του RMF και το αρχικό σύνολο δεδομένων εισόδου δίνονται ως είσοδος στο Velvet το οποίο βασίζεται στον χειρισμό των γραφημάτων de Bruijn, μέσω της αφαίρεσης σφαλμάτων και της απλοποίησης επαναλαμβανόμενων περιοχών, προκειμένου να επεξεργαστεί τη συναρμολόγηση και να δώσει τις ακολουθίες εξόδου. Ο συνολικός σχεδιασμός περιλάμβανε την επεξεργασία συναρμολόγησης γονιδιώματος που κέρδισε μια ταχύτητα της τάξης του 2x-6x, με καλή ποιότητα στα αποτελέσματα μεταξύ των δύο μεθόδων.el
ΤύποςΔιπλωματική Εργασίαel
ΤύποςDiploma Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by-nc-sa/4.0/en
Ημερομηνία2021-09-14-
Ημερομηνία Δημοσίευσης2021-
Θεματική ΚατηγορίαFPGA acceleratorel
Θεματική ΚατηγορίαGenome assemblyel
Θεματική ΚατηγορίαΣυστοιχία γονιδιώματοςel
Θεματική ΚατηγορίαΦιλτράρισμα συνόλου δεδομένωνel
Θεματική ΚατηγορίαDataset filteringel
Θεματική ΚατηγορίαVelveten
Θεματική ΚατηγορίαΓράφοι de Bruijnel
Θεματική Κατηγορίαde Bruijn graphsel
Βιβλιογραφική ΑναφοράGeorgios Galanos, "Hardware acceleration of genome assembly algorithms", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2021en
Βιβλιογραφική ΑναφοράΓεώργιος Γαλανός, "Επιτάχυνση μέσω υλικού (hardware) αλγορίθμων για συστοιχία γονιδιώματος", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021el

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά