Grant: Discovery Grants Program - Individual

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.