Computational Techniques for Applications in Bioinformatics and Coding Theory

生物信息学和编码理论应用的计算技术

• 批准号: RGPIN-2014-04322
• 负责人: Houghten, Sheridan
• 金额: $ 1.46万
• 依托单位: Brock University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=566444
• 关键词: Computational; Techniques; Applications; Bioinformatics; Coding

When faced with a difficult scientific problem, the number of possible solutions to consider can be overwhelming. Using a computational search makes it possible to attack problems that would otherwise be too difficult. In a computational search we explore the enormous space of possible solutions to produce results. But not all searches will produce results in a reasonable time: from a Computer Science standpoint, the true problem becomes one of determining how best to manage the search space. To be effective, a combination of strategies must be used. My main objective is to develop and evaluate algorithms and methodologies for computational searches. These will be applied to difficult problems in Bioinformatics and Coding Theory, of importance not only for theoretical reasons but also because of real-world applications. In each case, determining the appropriate algorithms and methodologies will allow us to obtain solutions that would otherwise be unattainable. In Bioinformatics, algorithms relating to DNA sequencing and protein modeling will be developed. DNA sequencing technologies are rapidly advancing and have application in developing personalized medicine. Current sequencing technologies do not allow for an entire genome to be sequenced in one piece; rather, the genome is broken into small pieces that must be reassembled. The success of sequencing technologies relies on the accuracy of the computational techniques employed in assembly. In modeling a protein we are conducting a search, over an enormous search space, to try to find the best arrangement of the protein’s components in space. This may mean trying to find a model that provides a good match to other data, or one that has the lowest energy. Modeling a protein’s structure is crucial to understanding its function. Error-correcting codes have an incredibly wide range of applications. Traditionally used as a means of ensuring reliable transmission of data, it has been realized that they are of use in numerous other areas, including DNA sequencing, flash memories, quantum computing, DNA computing, and many more. The wide range of newer applications, however, requires in turn a variety of codes that in many cases differ significantly from traditional codes. Searching for the best codes for different situations is one of the main tasks that I will undertake. Some codes are mathematically impossible; however, determining whether this is the case is often a difficult task. For some codes, their existence is a long-standing open question. To use codes successfully, one must also address the issue of decoding – correcting errors when they occur. In all of the problems to be considered, the problem structure and search space must be carefully analyzed to determine an appropriate search strategy. We differentiate between searches in which we wish to find all solutions satisfying a set of predefined criteria, and those in which we wish to find one or several optimal solutions. In the first case, we have no choice but to consider the entire search space, although by applying restrictions based on domain knowledge we can eliminate infeasible solutions and drastically reduce its size; here, exhaustive searches using combinatorial techniques are appropriate. In the latter case, it may not be necessary to examine the entire search space, particularly if the problem does not require a solution that is guaranteed to be the best but rather one that is the best known; here, metaheuristics such as evolutionary algorithms are to be considered.

当面对一个困难的科学问题时，要考虑的可能解决方案的数量可能是压倒性的。使用计算搜索使得解决那些原本很难解决的问题成为可能。在计算搜索中，我们探索可能的解决方案的巨大空间，以产生结果。但并不是所有的搜索都会在合理的时间内产生结果：从计算机科学的角度来看，真正的问题是如何最好地管理搜索空间。为了取得成效，必须采用多种战略相结合的办法。我的主要目标是开发和评估计算搜索的算法和方法。这些将被应用于生物信息学和编码理论中的困难问题，不仅因为理论原因，而且因为实际应用的重要性。在每种情况下，确定适当的算法和方法将使我们能够获得否则无法实现的解决方案。在生物信息学中，将开发与DNA测序和蛋白质建模相关的算法。DNA测序技术正在迅速发展，并已应用于开发个性化医疗。目前的测序技术不允许将整个基因组以一个片段进行测序;相反，基因组被分解成必须重新组装的小片段。测序技术的成功依赖于组装中采用的计算技术的准确性。在对蛋白质建模时，我们在一个巨大的搜索空间中进行搜索，试图找到蛋白质组分在空间中的最佳排列。这可能意味着试图找到一个与其他数据匹配良好的模型，或者一个能量最低的模型。蛋白质结构建模对于了解其功能至关重要。纠错码有着非常广泛的应用。传统上被用作确保数据可靠传输的手段，人们已经意识到它们在许多其他领域都有用途，包括DNA测序、闪存、量子计算、DNA计算等等。然而，新的应用范围广泛，反过来又需要各种各样的代码，在许多情况下，这些代码与传统代码有很大的不同。为不同的情况寻找最好的代码是我将承担的主要任务之一。有些代码在数学上是不可能的;然而，确定是否是这种情况往往是一项困难的任务。对于某些守则，它们的存在是一个长期悬而未决的问题。为了成功地使用代码，还必须解决解码问题--当错误发生时进行纠正.在所有要考虑的问题中，必须仔细分析问题结构和搜索空间，以确定适当的搜索策略。我们区分搜索，我们希望找到满足一组预定义的标准的所有解决方案，和那些我们希望找到一个或几个最佳解决方案。在第一种情况下，我们别无选择，只能考虑整个搜索空间，尽管通过应用基于领域知识的限制，我们可以消除不可行的解决方案，并大大减少其大小;在这里，使用组合技术的穷举搜索是合适的。在后一种情况下，可能没有必要检查整个搜索空间，特别是如果问题不需要保证是最好的解决方案，而是一个最好的解决方案;这里，要考虑进化算法等元算法。