Algorithms and Structure of Theoretical and Natural Computing Models

自然计算领域研究受自然启发的不同计算模型。这一领域的一些主要目标是以数学形式对过程进行形式化，研究模型的性质，创建算法以根据所展示的特征分析数据，并创建过程的计算机模拟。所有这些都有助于更好地理解自然系统本身。我们的研究小组对涉及DNA和其他序列的自然和理论计算模型特别感兴趣，并研究它们如何随着时间的推移而变化，以响应各种机械和操作。 以前人们认为，一个人的基因组在一生中很少发生变化。在一种名为纤毛虫的生物中发现了一个例外，已知这种生物经历了一个复杂的程序化DNA重排过程。这一过程即使用计算机也很难完成，但纤毛虫已经通过这种机制存活了数百万年。其他类型的基因组重排现在也在其他生物如鱼中被发现，甚至在与疾病有关的人类中也被发现。通常，在一个生物体中研究各种新的机制可以部分地将知识转化为其他物种，因此了解纤毛虫的程序性基因组重排是重要的。我们感兴趣的是使用形式主义、数学和模拟来使用计算机研究纤毛虫，然后将这些知识转化为生物学。 另一个在整个进化过程中改变DNA的过程是通过转座元件发生的，转座元件可以将自己从基因组的一个位置剪切、粘贴或复制到另一个位置。这些元素占我们基因组的比例惊人地大(约50%)，在某些植物中甚至更多。我们感兴趣的是建立它们随时间和跨多个物种移动的真实模拟，然后创建预测转座元件移动历史的算法。这些元素对于理解物种是如何产生的很重要，并在基因疗法中具有潜力，基因疗法涉及改变活的有机体的DNA，通常用于治疗疾病。 我们也有兴趣研究序列可能改变的常见方式，例如片段的删除，或者序列之间片段的并行“洗牌”或交织，并评估它们对计算的影响。这包括数学分析，研究什么可以用算法来解决，以及分析复杂性。这将为研究许多涉及缺失和改组的过程创造一个一般的框架，例如纤毛虫的重排过程，鱼类的缺失过程，以及其他尚未发现的过程。

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.