Η ριβονουκλεάση P είναι το ένζυμο το οποίο αναλαμβάνει την δημιουργία του 5´ ώριμου άκρου όλων των πρόδρομων μορίων tRNA. Πρόκειται για ένα ριβονουκλεο-πρωτεϊνικό σύμπλοκο το οποίο εντοπίζεται στα κύτταρα των οργανισμών και από τις τρεις κύριες φυλογενετικές περιοχές, τα Βακτήρια, τα Αρχαία και τους Ευκαρυώτες. Αποτελείται από μια υπομονάδα RNA απαραίτητη για την κατάλυση, ενώ το μέγεθος και ο αριθμός των πρωτεϊνικών υπομονάδων ποικίλλει από μια μικρή στα βακτήρια έως δέκα πρωτεΐνες στο ολοένζυμο που απομονώνεται από τα ανθρώπινα κύτταρα. Η υπομονάδες RNA των βακτηρίων καθώς επίσης και μερικών αρχαίων μπορούν να καταλύσουν την αντίδραση ωρίμανσης του tRNA απουσία της πρωτεΐνης in vitro, είναι δηλαδή ριβοένζυμα. Η ανακάλυψη αυτή διεύρυνε τις αντιλήψεις μας για τις ιδιότητες των βιομορίων και επανέφερε στο προσκήνιο την θεωρία του κόσμου του RNA. Στο ευκαρυωτικό ριβοένζυμο, ο ρόλος των πρωτεϊνών είναι πιο ουσιαστικός, καθώς η υπομονάδα RNA φαίνεται ότι χάνει μεγάλο μέρος της λειτουργικής της ανεξαρτησίας. Η διαλεύκανση των λειτουργών της κάθε υπομονάδας θα δώσει σημαντικές πληροφορίες για την εξέλιξη της RNase P από ένα αρχέγονο ένζυμο σε ένα πολύπλοκο ριβονουκλεοπρωτεϊνικό σύμπλοκο. Η RNase P από το Dictyostelium discoideum διαθέτει μια απαραίτητη για την δραστικότητα υπομονάδα RNA όπως και όλα τα ένζυμα αυτού του είδους. Παράλληλα διαθέτει έντονο πρωτεϊνικό χαρακτήρα καθώς διαθέτει την χαμηλότερη πυκνότητα επιπολής σε σχέση με ένζυμα RNase P από άλλους οργανισμούς. Οι πληροφορίες αυτές προέρχονται από τον αρχικό χαρακτηρισμό του ενζυμικού συμπλόκου, και δεν παρέχουν στοιχεία για την ακριβή σύστασή του. Στην παρούσα μελέτη, πραγματοποιήθηκε κλωνοποίηση και χαρακτηρισμός ενός από τα γονίδια που εντοπίστηκαν στο γονιδίωμα του Dictyostelium, ομόλογα προς χαρακτηρισμένα γονίδια από τον άνθρωπο και άλλους ευκαρυώτες. Το γονίδιο drpp30 κωδικεύει μια πρωτεΐνη 40.7 kDa, σημαντικά μεγαλύτερη από τις ομόλογες της. Η πρωτεΐνη DRpp30 υπερεκφράστηκε σε βακτηριακά κύτταρα, και μετά τον χρωματογραφικό καθαρισμό της χρησιμοποιήθηκε για την παρασκευή πολυκλωνικών αντισωμάτων. Η συμμετοχή της DRpp30 στο μακρομοριακό σύμπλοκο της RNase P πιστοποιήθηκε με ανοσοβιοχημική προσέγγιση, ενώ η ανασυνδυασμένη πρωτεΐνη προσδένει τo pre-tRNA υπόστρωμα του ενζύμου, καθώς και την υπομονάδα RNA in vitrο. Το μοντέλο ομολογίας της DRpp30 βάσει της κρυσταλλικής δομής της ορθόλογης Ph1877 από τα αρχαία, φανερώνει ότι η πρωτεΐνη αποκτά τη δομή αβ βαρελιού (ΤΙΜ barrel fold). Κατά τη διάρκεια της διατριβής, οι προσπάθειες για τον εντοπισμό του γονιδίου της RNA υπομονάδας ήταν σε εξέλιξη, όταν το εν λόγω γονίδιο αναγνωρίστηκε μέσω φυλογενετικών συγκρίσεων από την ομάδα του Norman Pace. Το μετάγραφο του γονιδίου εντοπίστηκε σε ενεργά κλάσματα RNase P, και παράλληλα εντοπίστηκε και ένα μικρότερο μετάγραφο του ίδιου γονιδίου. Προσδιορίστηκαν τα ακριβή 5´και 3´ άκρα των δύο αυτών μορίων και ακολούθησε κλωνοποίηση τους. Τα in vitro μετάγραφα των δύο κλωνοποιημένων αλληλουχιών μπορούν να υποκαθιστούν την ενδογενή RNA υπομονάδα του ολοενζύμου in vitro, ενώ δεν εντοπίστηκε έως τώρα ενζυμική δραστικότητα που να σχετίζεται με τα δύο αυτά μόρια. / Ribonuclease P is a ubiquitus ribonucleoprotein enzyme, responsible for the production of the 5´ mature ends of all precursor tRNA molecules. RNase P endonucleolytic activity has been isolated from organisms representing the three domains of life, namely Bacteria, Archaea and Eukarya. It has been shown to contain an essential RNA subunit and one (Bacteria) or more (Archaea, Eukaryotes) proteins. The RNase P RNA subunits from bacteria and some archaea are catalytically active in vitro, whereas those from eukaryotes and most archaea have lost most of their functionality and require protein subunits for activity. RNase P has been characterized biochemically and genetically in several systems, and structures for both RNA and protein subunits have emerged. The integration of structural and functional data is slowly forming a scenario for the evolution of RNase P from an ancient enzyme to a highly organized ribonucleoprotein complex. Dictyostelium discoideum RNase P harbors an essential RNA subunit, and has high protein content, as judged by its low boyant density. Nevertheless, our knowledge on the exact composition was limited. In the current study, a gene showing significant similarity to human Rpp30 RNase P protein subunit was identified in Dictyostelium genome. The gene encodes a protein (DRpp30) which is significantly larger than its homologues, due to an unusual C-terminus. The gene was cloned, overexpressed, and was used for the production of polyclonal antibodies. The participation of DRpp30 in the macromolecular complex of RNase P was verified by an immunobiochemical approach. The recombinant protein was shown to bind specifically both the RNase P RNA subunit and the pre-tRNA substrate in vitro, thus giving a first insight of its role in the holoenzyme complex. Homology modeling using as a template the archaeal Ph1887p, and molecular dynamics simulations of the modeled structure suggest that DRpp30 adopts a TIM-barrel fold. While our efforts to isolate the gene encoding the RNA subunit of D. discoideum RNase P were in progress, Norman Pace and his group identified it through phylogenetic comparison. The full transcript of the gene was detected in active RNase P samples along with a smaller transcript of the same gene. The exact 5´and 3´ ends of both transcripts were identified and were cloned. Both these transcripts can substitute the endogenous RNA subunit in vitro, but no enzymatic activity associated with these RNA molecules could be detected so far.

Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 110 δεκαδικών ψηφίων είναι ο General Number Field Sieve (GNFS). Ο αλγόριθμος αυτός είναι ο καρπός πολλών ετών έρευνας, κατά τη διάρκεια της οποίας παράγονταν ολοένα και ταχύτεροι αλγόριθμοι για να καταλήξουμε μέχρι στιγμής στον αλγόριθμο GNFS. Πρωταρχικός σκοπός της παρούσης μεταπτυχιακής εργασίας είναι η παρουσίαση του θεωρητικού μαθηματικού υπόβαθρου πάνω στο οποίο βασίζεται ο GNFS καθώς και η ακολουθιακή υλοποίηση της βασικής εκδοχής του αλγορίθμου. Ως γλώσσα υλοποίησης επιλέχθηκε η C++. Η υλοποίηση έγινε σε συνεργασία με τον συμφοιτητή μου και αγαπητό φίλο Χρήστο Μπακογιάννη, όπου στα πλαίσια της μεταπτυχιακής του εργασίας πραγματοποιήθηκε η μεταφορά της ακολουθιακής υλοποίησης του αλγορίθμου σε παράλληλο κατανεμημένο περιβάλλον χρησιμοποιώντας το Message Passing Interface (MPI). Ο πηγαίος κώδικας της υλοποίησης καθώς και σχετικές πληροφορίες υπάρχουν online στη σελίδα http://kmgnfs.cti.gr. Σημειώνεται πως για την ευκολότερη και απρόσκοπτη ανάγνωση της εργασίας αυτής, ο αναγνώστης θα πρέπει να έχει ένα βαθμό εξοικείωσης με βασικές έννοιες της θεωρίας αριθμών, της αλγεβρικής θεωρίας αριθμών και της γραμμικής άλγεβρας. / Many public-key cryptosystems build their security on our inability to factor very large integers. The General Number Field Sieve (GNFS) is the most efficient, and at the same time most complex, classical known algorithm for factoring integers larger than 110 digits. This algorithm is the result of many years of research, during which, faster and faster algorithms were developed finally winding up to the development of the GNFS. The main purpose of this master thesis is the presentation of the mathematical ideas, on which the GNFS was developed, as well as a sequential implementation of the basic version of the algorithm. C++ was the language of choice. The implementation took place in collaboration with my colleague and dear friend Christos Bakogiannis, where as part of his master thesis, a distributed implementation of the algorithm using Message Passing Interface (MPI) was also developed. The source code of the implementations is publicly available and can be found online at http://kmgnfs.cti.gr. It is presumed that the reader is familiar with basic concepts of number theory, algebraic number theory and linear algebra.

Τα Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) αποτελούν μία αρκετά πρόσφατη και πολλά υποσχόμενη νέα τεχνολογία που βρίσκει πληθώρα εφαρμογών. Λόγω της ευρύτατης εφαρμοσιμότητάς της και της προφανούς θέσης που βρίσκει στο σύγχρονο κατανεμημένο υπολογιστικό κόσμο, η επιστημονική τυπική θεμελίωση των νόμων που διέπουν αυτή τη νέα τεχνολογία καθίσταται απαραίτητη. Έτσι, έχουν προταθεί πολλά νέα υπολογιστικά μοντέλα για ΑΔΑ. Μία ειδική κατηγορία τέτοιων συστημάτων είναι τα Πρωτόκολλα Πληθυσμών (ΠΠ). Αυτά διέπονται από τρία ιδιαίτερα χαρακτηριστικά: Οι κόμβοι αίσθησης (πράκτορες) κινούνται παθητικά, δηλαδή δε μπορούν να ελέγξουν την κίνηση στην οποία υπόκεινται, η διαθέσιμη μνήμη κάθε κόμβου είναι πολύ περιορισμένη και οι πράκτορες αλληλεπιδρούν κατά ζεύγη. Έχει αποδειχθεί ότι ένα κατηγόρημα είναι υπολογίσιμο από το μοντέλο των ΠΠ εάν και μόνο εάν είναι ημιγραμμικό. Η κλάση των ημιγραμμικών κατηγορημάτων αποτελεί μία αρκετά μικρή κλάση. Στην παρούσα εργασία, βασικός μας στόχος είναι η επέκταση του μοντέλου των πρωτοκόλλων πληθυσμών με σκοπό το κέρδος σε υπολογιστική ισχύ. Πρώτα κάνουμε την παραδοχή ότι, πέρα των κόμβων αίσθησης, και οι ακμές του γραφήματος μπορούν να διατηρούν περιορισμένες καταστάσεις. Έτσι, σε ένα πλήρες γράφημα n κόμβων είναι σα να έχουμε προσθέσει Ο(n^2) επιπλέον θέσεις μνήμης οι οποίες διαβάζονται και γράφονται μόνο από τα άκρα της αντίστοιχης ακμής. Αποδεικνύουμε ότι το νέο μοντέλο, το οποίο καλούμε μοντέλο Πρωτοκόλλων Πληθυσμών με Διαμεσολαβητή, μπορεί να λειτουργήσει ως μία κατανεμημένη ανταιτιοκρατική μηχανή Turing (ΜΤ) που χρησιμοποιεί όλη τη διαθέσιμη μνήμη. Η μόνη διαφορά από μία συνήθη ΜΤ είναι ότι η συγκεκριμένη μηχανή υπολογίζει μόνο συμμετρικές γλώσσες. Πιο τυπικά, δείχνουμε ότι ένα κατηγόρημα είναι υπολογίσιμο από το νέο μοντέλο εάν και μόνο εάν είναι συμμετρικό και ανήκει στην NSPACE(n^2). Επιπλέον, μελετάμε και τη δυνατότητα του νέου μοντέλου να διαγιγνώσκει γλώσσες γραφημάτων (για γενικά γραφήματα). Εν συνεχεία, αγνοούμε τις καταστάσεις των ακμών και δίνουμε μία νέα βελτίωση και πάλι απευθείας απ' το μοντέλο των ΠΠ. Η υπόθεση που κάνουμε τώρα είναι ότι οι πράκτορες είναι πολυταινιακές ΜΤ με άπειρη μνήμη, που μπορούν τόσο να εκτελούν εσωτερικό υπολογισμό όσο και να αλληλεπιδρούν με άλλους πράκτορες και ορίζουμε χωρικά φραγμένους υπολογισμούς. Καλούμε το νέο αυτό μοντέλο, μοντέλο Παθητικά κινούμενων Μηχανών. Αποδεικνύουμε ότι αν χρησιμοποιείται σε κάθε πράκτορα μνήμη το πολύ f(n) για f(n)=Ω(log n) τότε ένα κατηγόρημα είναι υπολογίσιμο από το νέο μοντέλο εάν και μόνο εάν είναι συμμετρικό και ανήκει στην NSPACE(nf(n)). Δείχνουμε επίσης ότι αυτό δεν ισχύει για f(n)=o(log n). Βασιζόμενοι σε αυτά, δείχνουμε ότι για f(n)=Ω(log n) υπάρχει μία χωρική ιεραρχία ακριβώς όπως και για τις συνήθεις (συμμετρικές) ΜΤ. Δείχνουμε επίσης ότι αυτό δεν ισχύει για f(n)=o(loglog n), καθώς στην τελευταία περίπτωση η αντίστοιχη κλάση καταρρέει μέσα στην κλάση των ημιγραμμικών κατηγορημάτων, και τέλος ότι για f(n)=Ω(loglog n) η κλάση γίνεται αυστηρά μεγαλύτερη των ημιγραμμικών κατηγορημάτων. Αφήνουμε ανοικτό το πρόβλημα του τι ακριβώς συμβαίνει για χωρικά φράγματα f(n) τέτοια ώστε f(n)=Ω(loglog n) και f(n)=o(log n). / Wireless Sensor Networks (WSNs) constitute a recent and promising new technology that is widely applicable. Due to the applicability of this technology and its obvious importance for the modern distributed computational world, the formal scientific foundation of its inherent laws becomes essential. As a result, many new computational models for WSNs have been proposed. Population Protocols (PPs) are a special category of such systems. These are mainly identified by three distinctive characteristics: the sensor nodes (agents) move passively, that is, they cannot control the underlying mobility pattern, the available memory to each agent is restricted, and the agents interact in pairs. It has been proven that a predicate is computable by the PP model iff it is semilinear. The class of semilinear predicates is a fairly small class. In this work, our basic goal is to enhance the PP model in order to improve the computational power. We first make the assumption that not only the nodes but also the edges of the communication graph can store restricted states. In a complete graph of n nodes it is like having added O(n^2) additional memory cells which are only read and written by the endpoints of the corresponding edge. We prove that the new model, called Mediated Population Protocol model, can operate as a distributed nondeterministic Turing machine (TM) that uses all the available memory. The only difference from a usual TM is that this one computes only symmetric languages. More formally, we establish that a predicate is computable by the new model iff it is symmetric and belongs to NSPACE(n^2). Moreover, we study the ability of the new model to decide graph languages (for general graphs). The next step is to ignore the states of the edges and provide another enhancement straight away from the PP model. The assumption now is that the agents are multitape TMs equipped with infinite memory, that can perform internal computation and interact with other agents, and we define space-bounded computations. We call this the Passively mobile Machines model. We prove that if each agent uses at most f(n) memory for f(n)=Ω(log n) then a predicate is computable iff it is symmetric and belongs to NSPACE(nf(n)). We also show that this is not the case for f(n)=o(log n). Based on these, we show that for f(n)=Ω(log n) there exists a space hierarchy like the one for classical symmetric TMs. We also show that the latter is not the case for f(n)=o(loglog n), since here the corresponding class collapses in the class of semilinear predicates and finally that for f(n)=Ω(loglog n) the class becomes a proper superset of semilinear predicates. We leave open the problem of characterizing the classes for f(n)=Ω(loglog n) and f(n)=o(log n).