Optimizing algorithms for mathematical modeling in bioinformatics

Abstract

The Thesis consists of four (4) chapters:Chapter 1-Algorithms and Mathematical ModelingThis chapter provides definitions for biological macromolecules and mainly for the mathematical representations of RNA secondary structures. From the set of canonical pairs, it is clear that a given RNA sequence has many potential structures. In fact, the number of possible structures grows exponentially with the length of the RNA sequence. The challenge is to identify whether structure plays a functional role for a given RNA sequence and, if yes, to predict this functional RNA structure. A new ‘loopless’ permutation-based algorithm is introduced for the representation of closed RNA secondary structures, which generates the permutations on base-pairs of ‘k-noncrossing’ setting partitions. The proposed algorithm reduces the computational complexity of known similar techniques in O(n), using minimal change ordering and transposing of not adjacent elements. The corresponding programming code in C can be found in Appendix A. We also propose two efficient algorithms, for the generation of nested sets and for the transformation of the generating permutations on base-pairs of k-noncrossing setting partitions into Motzkin words. The RNA Interaction Problem was also studied, through the introduction of a new class of generalized Motzkin paths, the semi-elevated inverse generalized Motzkin peakless paths, concerning an optimal representation of joint RNA secondary structures. The proposed technique makes it possible to extend close secondary structures without peaks towards the 3’ direction ignoring any steps of the form ud. In this first chapter we review biochemical reactions, cell ion channels, cell apoptosis and mitochondrial dynamics and while mitochondria are significantly reduced in Alzheimer’s disease, we determine an alternative representation of inner mitochondrial membrane through the Motzkin generalized paths in order to control and maximize the continuously fission machinery. Especially for the case of mitochondrial fusion we define a stochastic model through the Ambient Calculus for the representation and simulation of mitochondrial merging (between membranes, nucleic acids, genes and proteins). The corresponding programming pseudo code in BioAmbient Calculus can be found in Appendix B.Chapter 2-Artificial Intelligence TechniquesIn this chapter we review several approaches of machine learning techniques in Biological representations, statistical inference, Bayesian methods, logical inference, genetic algorithms, patterns representations and Case-Based Reasoning (CBR) systems. We give a short representation of nervous system and few models of artificial neural networks. Based on the above and having into consideration the RNA secondary structures’ representations of the previous chapter, we represent the RNA secondary prediction problem as a neural network which can be approached using the theory of the Travelling Salesman Problem (TSP). Although both problems are NP-Complete, many heuristics methods and genetic algorithms, such as ant colony optimization (ACO) for the TSP are known (not studied in this thesis).Additionally, based on the general CBR cycle processing for the adaption of its structural component (Retrieve, Reuse, Revise and Retain), we designed the theoretical framework of a CBR System in order to response and manage the information concerning sequential terms of biological structures and the implementation of pattern recognition on secondary structures. While problems concerning representations of certain biological structures like secondary structures, either are characterized as NP-complete or with high complexity, we proposed a theoretical combination of a machine-learning technique, with the basic Combinatorics terminology and the Longest Common Subsequent (LCS) method as a suitable and user friendly solution for accessing biological data and manage pattern recognition and mathematical modeling. Chapter 3-Applications in BiomedicineConsidering the latest researches, disruptions in the regulation of mitochondrial dynamics, low energy production, increased reactive oxygen species and mtDNA damage are relevant to human diseases, mainly in neurogenerative diseases. In this chapter we review several mechanisms of neurogenerative diseases like protein misfolding and mitochondrial malfunction. While recent studies have already prove the significant connection between mitochondrial dysfunction and human diseases and the disruptions of energy production due to inappropriate topological structure, we present a new theoretical mechanism concerning the formulation of the high energy concentration in mitochondrial inner membrane, characterizing the internal mitochondrial membrane as a natural superconductor, where electrical resistance of exactly zero occurs in certain temperature; nevertheless the creation of electric complexes into the inner mitochondrial membrane due to the unusual concentration of protons disrupts the normal flow of electrons and the production of ATP. Therefore, we proposed the term ‘electric thromboses’ for the explanation of these inadequate electrons’ flow, presenting simultaneously a natural mechanism of this important and unique phenomenon. Chapter 4-BioethicsIn this last chapter we discussed several aspects concerning the effects of artificial biomedical applications, considering the upcoming post humanism period. While the challenge of constructing Nano devices that imitate the operations of cell and other biological systems seems more realistic through the successful efforts in the synthesis and manufacturing of Nano scale materials and the combination of Bioinformatics, the variability in the ideological use of such concepts is associated with bioethical issues and several legal aspects. The convergence of bioethics and computer ethics, attempts to illustrate and approach problems, occurring by the fusion of human and machine, like clinical issues, privacy, confidentiality in medical diagnosis, directed individualized treatment or even more subjects of criminality and immortality, human dignity and justice or even industrial cost. The ethical considerations of innovating technologies have to be announced and explained to the social target groups. Therefore, it is ethically desirable to determine whether new artificial types of prognosis or treatment will be more effective and safe for humans when compared to conventional ones. Undoubtedly artificial bio-technologies will deliver a variety of improvements or a technological and healthcare revolution. The main problem is to study at early stage any social side effects.

Η εργασία αποτελείται από τέσσερα (4) κεφάλαια:Κεφάλαιο 1-Αλγόριθμοι και Μαθηματικά ΜοντέλαΤο κεφάλαιο αυτό παρέχει ορισμούς για τα βιολογικά μακρομόρια και κυρίως για τις μαθηματικές αναπαραστάσεις των δευτεροταγών δομών RNA. Από το σύνολο των κανονικών ζευγών, είναι σαφές ότι μια συγκεκριμένη ακολουθία RNA έχει πολλές πιθανές δομές. Στην πραγματικότητα, ο αριθμός των πιθανών δομών αυξάνεται εκθετικά με το μήκος της ακολουθίας RNA, οπότε θεωρείται πρόκληση ο προσδιορισμός του ρόλου της δομής και η πρόβλεψη της πιθανής λειτουργίας του. Παρουσιάζεται ένας νέος ‘loopless’ αλγόριθμος παραγωγής μεταθέσεων για την αναπαράσταση κλειστών δευτεροταγών δομών RNA, ο οποίος μειώνει την πολυπλοκότητα σε O(n), κάνοντας μόνο αντιμεταθέσεις μη γειτονικών ζευγών. Ο αντίστοιχος κώδικας του προγράμματος σε C μπορεί να βρεθεί στο Παράρτημα Α της εργασίας αλλά και στο εργαστήριο του τμήματος CMODLAB. Προτείνονται επίσης δύο νέοι αλγόριθμοι, για την παραγωγή ένθετων συνόλων (nested sets) και Motzkin λέξεων από τις προαναφερθείσες παραγόμενες μεταθέσεις. Παρουσιάζεται μια νέα κατηγορία Motzkin μονοπατιών για την αναπαράσταση του προβλήματος της αλληλεπίδρασης δύο μορίων RNA (joint RNA sequences), τα λεγόμενα semi-elevated inverse generalized Motzkin peakless paths. Η προτεινόμενη τεχνική καθιστά δυνατή την επέκταση μιας δευτεροταγούς δομής χωρίς κορυφές προς την κατεύθυνση του 3' άκρου του RNA, αγνοώντας βήματα της μορφής du. Στο πρώτο κεφάλαιο παρουσιάζονται επίσης στοιχεία ηλεκτροφυσιολογίας καθώς και απόπτωσης των κυττάρων αλλά και οι λεγόμενες μιτοχονδριακές λειτουργίες. Επίσης αναπαρίσταται η εσωτερική μεμβράνη του μιτοχονδρίου μέσω των Motzkin μονοπατιών και συνδέεται η εναλλακτική αυτή παρουσίαση με νευρολογικές διαταραχές όπως η νόσος του Alzheimer. Τέλος σχεδιάστηκε ένα στοχαστικό μοντέλο με την Άλγεβρα BioAmbient για την αναπαράσταση της διαδικασίας της συγχώνευσης δύο ανεξάρτητων μιτοχονδρίων σε ένα (μεμβράνες, νουκλεϊκά οξέα, γονίδια και πρωτεΐνες). Ο αντίστοιχος ψευδοκώδικας σε BioAmbient μπορεί να βρεθεί στο Παράρτημα Β της εργασίας.Κεφάλαιο 2-Τεχνητή Νοημοσύνη Σε αυτό το κεφάλαιο παρουσιάζονται διάφορες προσεγγίσεις των τεχνικών μηχανικής μάθησης σε Βιολογικές παραστάσεις όπως στατιστική συμπερασματολογία, Bayesian μέθοδοι, λογική συμπερασματολογία, γενετικοί αλγόριθμοι, pattern recognition και Case-Based Reasoning (CBR) συστήματα. Δίνουμε μια σύντομη αναπαράσταση του νευρικού συστήματος και μοντέλα τεχνητών νευρωνικών δικτύων. Ως εφαρμογή των νευρωνικών δικτύων και σε συνέχεια του 1ου κεφαλαίου προτείνεται η τεχνική του TSP (Πρόβλημα Περιοδεύοντος Πωλητή) στην αναπαράσταση κλειστών δευτεροταγών δομών RNA. Αν και τα δύο προβλήματα θεωρούνται NP-complete, πολλές μέθοδοι heuristics και γενετικοί αλγόριθμοι, όπως η βελτιστοποίηση ACO (Ant Colony Optimization) για το TSP είναι γνωστές (οι οποίες δεν είναι αντικείμενο μελέτης της εργασίας). Επιπλέον, έχοντας υπόψη το βασικό κύκλο ενός CBR συστήματος (Retrieve, Reuse, Revise and Retain), σχεδιάστηκε το θεωρητικό πλαίσιο μιας τροποποιημένης εφαρμογής CBR για την αποθήκευση και διαχείριση πληροφοριών που σχετίζονται με την αναπάρασταση βιολογικών δομών και την εφαρμογή της αναγνώρισης προτύπων κυρίως στις δευτεροταγείς δομές RNA. Η εν λόγω εφαρμογή αποτελεί μια θεωρητική προσέγγιση της τεχνικής μηχανικής μάθησης (machine learning), με τη Συνδυαστική (combinatorics) και τη μέθοδο LCS (longest common subsequent).Κεφάλαιο 3-Εφαρμογές στη ΒιοϊατρικήΛαμβάνοντας υπόψη τις πιο πρόσφατες έρευνες, οι διαταραχές στη λειτουργία των μιτοχονδρίων, η χαμηλή παραγωγή ενέργειας, οι μεταλάξεις στο mtDNA κ.α. σχετίζονται με ανθρώπινες ασθένειες, όπως οι λεγόμενες εκφυλιστικές νόσοι. Σε αυτό το κεφάλαιο παρουσιάζονται διάφοροι μηχανισμοί νευρολογικών διαταραχών όπως η λανθασμένη αναδίπλωση πρωτεϊνών και η μιτοχονδριακή δυσλειτουργία. Ενώ οι ερευνητές έχουν ήδη αποδείξει τη συσχέτιση μεταξύ της δυσλειτουργίας των μιτοχονδρίων, των νευρολογικών ασθενειών και των διαταραχών της παραγωγής ενέργειας ATP που οφείλονται σε λανθασμένη τοπολογικά εσωτερική δομή (λόγω σφαλμάτων στις λειτουργίες του fission & fusion), παρουσιάζουμε ένα νέο θεωρητικό μηχανισμό σχετικά με τη διαμόρφωση της υψηλής συγκέντρωσης ενέργειας στην εσωτερική μεμβράνη των μιτοχονδρίων, χαρακτηρίζοντας την εσωτερική μιτοχονδριακή μεμβράνη ως φυσικό υπεραγωγό. Το φαινόμενο αυτό της ‘ηλεκτρικής θρόμβωσης’ είναι υπεύθυνο για τη δημιουργία ηλεκτρικών συμπλεγμάτων στην εσωτερική μιτοχονδριακή μεμβράνη καθώς παρουσιάζεται ασυνήθιστα μεγάλη συγκέντρωση πρωτονίων η οποία και διαταράσσει τη φυσιολογική ροή των ηλεκτρονίων και την παραγωγή της ATP. Κεφάλαιο 4-ΒιοηθικήΓίνεται μια σύντομη αναφορά σε ηθικά ζητήματα που άπτονται της εξέλιξης των βιολογικών τεχνολογιών, από το συνδυασμό επιστημών όπως η Νανοτεχνολογία και η Βιοπληροφορική, και παρουσιάζονται συγκεκριμένες περιπτώσεις κοινωνικών προεκτάσεων που έχει η εφαρμογή της τεχνητής νοημοσύνης στη Βιοϊατρική αλλά και η επερχόμενη εποχή του Μετα-Ανθρωπισμού. Η χρήση συσκευών Ναονοτεχνολογίας που μιμούνται τη λειτουργία του κυττάρου και άλλα βιολογικά συστήματα σε συνδυασμό με τα επιτεύγματα της βιοπληροφορικής αναδεικνύουν θέματα βιοηθικής και άλλα νομικά ζητήματα καθώς και προβλήματα δεοντολογίας όπως η ένωση ανθρώπου και μηχανής, θέματα κλινικών μελετών και κόστους, προστασία της ιδιωτικής ζωής, εμπιστευτικότητας στην ιατρική διάγνωση, στη δυνατότητα εξατομικευμένης θεραπείας ή ακόμα περισσότερο θέματα εγκληματικότητας και ανθρώπινης αθανασίας, ανθρώπινης αξιοπρέπειας και δικαιοσύνης.