Efficient Representation and Manipulation of Large-Scale Biological Sequence Data

生物分子序列的存储和访问以确定序列同源性是当前生物信息学和计算生物学革命的核心。除了搜索工具外，一些重要应用程序使用的大量生物数据突显了开发高效的核外算法的必要性。该项目的目标是设计磁盘驻留序列数据的存储结构、算法技术和软件，并将其应用于计算生物学中的重要应用。为了实现这一目标，我们使用了一个三管齐下的策略：首先，与领域专家合作确定的应用需求被用来设计序列数据的基本存储结构。这项研究包括为众所周知的核内数据结构开发高效的核外算法，以及设计适合目标应用的新数据结构。其次，正在开发对驻留在磁盘上的序列数据进行高效查询的算法。最后，将开发的核心外技术与计算基因组学中的应用软件集成，如EST聚类法和片段拼接。其目标是开发更快的算法，减少过高的主存需求，或酌情解决更大的问题实例。研究结果将以软件库的形式提供给计算机科学家，并以应用软件的形式提供给分子生物学家。正在努力将这项研究的结果纳入分子生物学家使用的流行工具中。该项目的跨学科性质为研究生提供了独特的培训机会。

ABSTRACTStorage of biomolecular sequences, and accessing them to determine sequence homologies is central to the current revolution in bioinformatics and computational biology. Besides search tools, the large size of biological data used by some important applications underscores the need for developing efficient out-of-core algorithms. The goal of the project is to design storage structures, algorithmic techniques, and software for disk-resident sequence data, and apply it to important applications in computational biology. To achieve thisgoal, a three-pronged strategy is used: Firstly, application requirements identified in collaboration with domain experts are being used to design fundamental storage structures for sequence data. This research spans the development of efficient out-of-core algorithms for well-known in-core data structures and also the design of new data structures suitable for targeted applications. Secondly, efficient algorithms for queries on disk-resident sequence data are being developed. Finally, the out-of-core techniques developed are integrated with application software in computational genomics such as EST clustering and fragment assembly. The goal is to develop faster algorithms, reduce the exorbitant main-memory requirements, or enable solution of larger problem instances, as appropriate.The results of the research will be made accessible to computer scientistsin the form of software libraries and molecular biologists in the form of application software. Efforts are being made to integrate the results of this research into popular tools used by molecular biologists. The interdisciplinary nature of the project is providing unique training opportunities for graduate students.