Algorithms and Structure of Theoretical and Natural Computing Models

理论和自然计算模型的算法和结构

• 批准号: RGPIN-2016-06172
• 负责人: McQuillan, Ian
• 金额: $ 1.89万
• 依托单位: University of Saskatchewan
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=659434
• 关键词: Algorithms; Structure; Theoretical; Natural; Computing

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.**

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