Algorithms and Structure of Theoretical and Natural Computing Models

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

• 批准号: RGPIN-2016-06172
• 负责人: McQuillan, Ian
• 金额: $ 1.89万
• 依托单位: University of Saskatchewan
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=616141
• 关键词: 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，通常用于治疗疾病。 我们也有兴趣研究序列可以改变的常见方式，例如片段的删除，或并行“改组”或序列之间片段的交错，并评估它们对计算的影响。这涉及数学分析、研究可以用算法解决的问题以及分析复杂性。这将为研究涉及删除和洗牌的许多过程创建一个通用框架，例如纤毛虫的重排过程、鱼类的删除以及其他尚未发现的过程。