Computational Techniques for Applications in Bioinformatics and Coding Theory

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

• 批准号: RGPIN-2014-04322
• 负责人: Houghten, Sheridan
• 金额: $ 1.46万
• 依托单位: Brock University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=610963
• 关键词: 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计算等。然而，较新应用的广泛范围反过来需要各种代码，这些代码在许多情况下与传统代码显著不同。为不同情况寻找最好的代码是我将承担的主要任务之一。有些代码在数学上是不可能的；然而，确定是否是这种情况通常是一项困难的任务。对于一些代码来说，它们的存在是一个长期悬而未决的问题。要成功地使用代码，还必须解决解码问题--在错误发生时进行纠正。 在所有要考虑的问题中，必须仔细分析问题的结构和搜索空间，以确定合适的搜索策略。我们区分搜索和搜索，前者希望找到满足一组预定义标准的所有解，后者希望找到一个或多个最优解。在第一种情况下，我们别无选择，只能考虑整个搜索空间，尽管通过应用基于领域知识的限制，我们可以消除不可行解并大大减小其大小；在这里，使用组合技术进行穷举搜索是合适的。在后一种情况下，可能没有必要检查整个搜索空间，特别是如果问题不需要保证是最好的解决方案，而是最知名的解决方案；在这里，将考虑诸如进化算法的元启发式算法。