ITR/AP (CISE) Collaborative Research: Best-First Search Algorithms for Sequence Alignment Problems in Computational Biology

计算生物学中序列比对问题的最优优先搜索算法分子生物学家目前面临着非常具有挑战性的计算问题。 例如，人类基因组的草图已经完成，大约有30亿个碱基对的序列。 老鼠基因组的草图很快就会完成。 我们知道老鼠和人类有超过90%的遗传物质相同。 我们不知道的是，人类和小鼠基因组的哪些部分是两个物种共有的。 这些信息可用于识别人类基因，并将小鼠研究的结果转化为人类健康和疾病的研究。 识别这两个DNA序列之间的共同元素的问题是序列比对的一个例子，这是一个计算问题。 序列比对问题的其他例子包括基因识别、RNA和蛋白质结构预测。 目前的计算机算法要么太慢，要么需要太多的内存，无法直接解决像人类-小鼠基因组序列比对这样大的问题。 我们建议开发各种序列比对问题的新算法，基于人工智能中的启发式搜索算法。 我们的目标是提供更有效的序列比对算法供分子生物学家使用。

AbstractZhang 0113618Korf 0113313Best-First Search Algorithms for Sequence Alignment Problems in ComputationalBiologyMolecular biologists are currently faced with very challenging computational problems. For example, a draft of the human genome has been completed, a sequence of about three billion base pairs. A draft of the mouse genome soon will be completed. We know that mice and men share over 90% of their genetic material. What we don't know is exactly which parts of the human and mouse genomes are common to both species. This information can be used to identify human genes, and to translate results from mouse studies to studies of human health and disease. The problem of identifying the common elements between these two DNA sequences is an example of sequence alignment, which is a computational problem. Other examples of sequence alignment problems include gene identification, and RNA and protean structure prediction. Current computer algorithms are either too slow, or require too much memory, to directly solve a problem as large as the human-mouse genomic sequence alignment. We propose to develop new algorithms for various sequence-alignment problems, based on heuristic search algorithms in artificial intelligence. Our goal is to provide much more efficient sequence-alignment algorithms for use by molecular biologists.