Algorithms and Structure of Theoretical and Natural Computing Models

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

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