Algorithms and Structure of Theoretical and Natural Computing Models

点击翻译按钮获取中文摘要

The area of natural computing investigates different models of computation inspired by nature. Some major objectives of this area are to formalize the processes mathematically, study properties of the models, create algorithms to analyze data from exhibited characteristics, and create computer simulations of the processes. These all contribute towards an improved understanding of the natural systems themselves. Our research group is especially interested in natural and theoretical models of computation involving DNA and other sequences, and examining how they change over time in response to various machinery and operations. It was previously believed that the genome of an individual changed very rarely over a lifespan. One exception that was found occurs in an organism called ciliates, which are known to undergo a complicated procedure of programmed DNA rearrangement. This process is difficult to accomplish even with a computer, yet ciliates have managed to survive for many millions of years with this mechanism. Other types of genomic rearrangements are now being found in other organisms such as fish, and even in humans as related to disease. Frequently, studying various novel mechanisms in one organism can partially translate knowledge to other species, and therefore it is important to understand programmed genomic rearrangements in ciliates. We are interested in using formalisms, mathematics, and simulations to study ciliates using computers, and then translate that knowledge back to biology. Another process that changes DNA throughout evolution occurs via transposable elements which can cut and paste or copy themselves from one position of a genome to another. These elements make up a surprisingly large fraction of our genome (roughly 50%), and even more in certain plants. We are interested in building a realistic simulation of their movement over time, and across multiple species, and then creating algorithms for predicting the history of transposable element movement. These elements are important to understanding how species are created, and have potential in gene therapy which involves changing the DNA of a living organism, usually to treat disease. We are also interested in studying common ways that sequences can change, such as the deletion of segments, or the parallel "shuffling" or interleaving of sections between sequences, and assessing their effects on computing. This involves mathematical analyses, studying what can be solved with algorithms, and analyzing the complexity. This will create a general framework for studying many processes involving deletion and shuffle, such as the rearrangement procedure in ciliates, deletion in fish, and others yet to be discovered.