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.