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

点击翻译按钮获取中文摘要

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.