Συντάχθηκε 06-02-2013 15:01
από Galateia Malandraki
Email συντάκτη: gmalandraki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος ΑΡΜΗΧ.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΒΑΣΙΛΗ ΠΑΠΑΔΗΜΗΤΡΙΟΥ
με θέμα
“ Κωδικοποίηση Διόρθωσης Σφαλμάτων για Αυτο-Συναρμολόγηση με Πλακίδια DNA”
“ Error-Correcting Encoding for Self-Assembly with DNA Tiles ”
Πέμπτη 7 Φεβρουαρίου 2013, 12μμ
Αίθουσα Εργαστηρίου Intelligence (141-A14-2), Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Επίκουρος Καθηγητής Μιχαήλ Γ. Λαγουδάκης (επιβλέπων)
Επίκουρος Καθηγητής Βασίλειος Σαμολαδάς
Επίκουρος Καθηγητής Άγγελος Μπλέτσας
Περίληψη
Καθώς η τεχνολογία υπολογιστών που βασίζεται στο πυρίτιο πλησιάζει τα όριά της, νέα πρότυπα υπολογισμού, όπως οι DNA και οι κβαντικοί υπολογιστές, αποκτούν όλο και περισσότερη προσοχή από την ερευνητική κοινότητα υπό το πρίσμα των δυνατοτήτων τους για επίλυση NP-δύσκολων προβλημάτων σπρώχνοντας την εκθετική χρονική διάσταση στο χώρο. Ο υπολογισμός με DNA διερευνά τη δυνατότητα της κωδικοποίησης δεδομένων και αλγοριθμικών διαδικασιών σε συνθετικές έλικες DNA και την αξιοποίηση των ιδιοτήτων συμπληρωματικότητας και μαζικού παραλληλισμού του DNA για την εκτέλεση υπολογισμών. Η αυτο-συναρμολόγηση πλακιδίων DNA επικεντρώνεται σε υπολογισμούς πλακόστρωσης, όπου τα πλακίδια μπορούν να προσαρτώνται το ένα στο άλλο μέσω προσεκτικά σχεδιασμένων απολήξεων για να δημιουργήσουν πολύπλοκες δομές που κωδικοποιούν επιθυμητούς υπολογισμούς. Ωστόσο, η τρέχουσα τεχνολογία αυτο-συναρμολόγησης πλακιδίων DNA περιορίζεται από την έλλειψη αξιοπιστίας και ανοχής σε σφάλματα, πράγμα που σημαίνει ότι κατά τη διάρκεια εργαστηριακών πειραμάτων εμφανίζονται πολλά σφάλματα στην αντιστοίχιση αλυσίδων και πλακιδίων DNA, καταστρέφοντας τελικά τον επιθυμητό υπολογισμό. Η παρούσα διπλωματική εργασία επικεντρώνεται σε μια σχεδίαση αυτο-συναρμολόγησης πλακιδίων DNA για περιοδικά πρότυπα/μοτίβα βασισμένα σε υπολογισμούς EXclusive-OR (XOR), η οποία είναι επιρρεπής σε σφάλματα που διαδίδονται σε όλη την συναρμολόγηση, και προτείνει δύο εναλλακτικές κωδικοποιήσεις/σχεδιάσεις που υλοποιούν αυτο-διόρθωση σφαλμάτων με διαφορετικές αναλογίες μεταξύ πολυπλοκότητας και αποτελεσματικότητας. Και οι δύο σχεδιάσεις βασίζονται στην εισαγωγή πλεονασμού στην αναπαράσταση πληροφορίας για τον εντοπισμό σφαλμάτων και πρόσθετων επιπέδων πλακιδίων για την διόρθωση σφαλμάτων. Οι προτεινόμενες σχεδιάσεις έχουν ως αποτέλεσμα τη δραστική μείωση της πιθανότητας ότι ένα σφάλμα θα διαδοθεί και θα αλλοιώσει το επιθυμητό πρότυπο/μοτίβο. Το μειονέκτημα των προτεινόμενων σχεδιάσεων είναι η μεγαλύτερη βιβλιοθήκη πλακιδίων και το αυξημένο συνολικό μέγεθος του πλέγματος συναρμολόγησης σε σχέση με τον αρχικό σχεδιασμό. Τα αποτελέσματα των προσομοιωμένων συναρμολογήσεων σύμφωνα με τις προτεινόμενες σχεδιάσεις επαληθεύουν την ιδιότητα της αυτο-διόρθωσης πολλών τύπων σφαλμάτων και δείχνουν μια σαφή μείωση της πιθανότητας διάδοσης σφαλμάτων στο πλέγμα της συναρμολόγησης.
Abstract
As silicon-based computer technology approaches its limits, new computing paradigms, such as DNA and quantum computing, gain more and more attention from the research community in light of their potential for solving NP-hard problems by pushing the exponential time dimension into space. DNA computing investigates the possibility of encoding data and algorithmic procedures in synthetic DNA strands and exploiting the complementarity and massive parallelism properties of DNA to perform computations. Self-assembly of DNA tiles focuses on tiling computations, whereby tiles can attach to each other through carefully-designed sticky ends to create complex structures that encode desired computations. However, current DNA tiling technology is limited by the lack of reliability and robustness, meaning that during laboratory experiments several errors occur in the pairing of DNA strands/tiles, ultimately ruining the desired computation. This thesis focuses on a DNA tiling design for EXclusive-OR (XOR)-based periodic ribbon patterns, which is susceptible to errors that propagate throughout the entire assembly, and proposes two alternative encodings/designs which implement error self-correction with different trade-offs between complexity and efficiency. Both designs rely on introducing redundancy in information representation for detecting errors and additional levels of tiles for correcting errors. The proposed designs result in a drastic decrease of the probability that an error will propagate and corrupt the desired ribbon pattern. The downside of the proposed designs is the larger tile library and the increased overall size of the assembly lattice compared to the original design. Our simulated assembly results under the proposed designs verify the property of self-correction for many types of errors and indicate a clear reduction of the probability of error propagation in the assembly lattice.
Συνημμένα:
-
2013-02-07-Papadimitriou-Announcement.doc
Μεταφορτώσεις: 202,
Μέγεθος: 51 KB application/octet-stream
