Algorithm design and analysis, web-database and web-server development in bioinformatics research driven by large volume data

算法设计和分析在计算机科学中起着核心作用。生物信息学和计算组学是新兴的跨学科研究领域，需要来自计算科学和生物科学的专业知识。一方面，生物学已经成为一门高通量的科学，其应用迫切需要先进的计算技术来消化大量的生物数据，以提供进一步的理解，从而导致新的生物学发现。另一方面，从生物应用中制定的计算问题的算法设计和分析的实践有助于提高我们对计算本质的理解，这可能会引发计算机科学的新革命。这项由大量生物学数据推动的拟议研究，恰恰具有这种双重意义。我们提出的研究目标应用是使用单核苷酸多态性（SNP）基因型数据进行全基因组连锁和关联研究（GWLAS），以及使用质谱数据进行全蛋白质组和全代谢组鉴定。在前者上，我们的目标是建立密集的SNP单倍型图谱，为恢复基于单倍型的GWLAS提供更精细和确定的单倍型等位基因信息。一旦成功，我们将能够突破基于基因型的GWLAS的瓶颈，特别是对牛基因组选择计划做出贡献。在后者方面，我们的目标是设计具有成熟性能的新算法来自动化肽鉴定和代谢物鉴定，以最有效地利用质谱数据。一旦成功，我们将能够使用全蛋白质组谱进行全基因组注释，以检测当前基因预测工具无法预测的新基因；我们还将能够使用整个代谢组定量分析来确定有效的生物标志物，以协助疾病诊断。我们的研究成果，包括整理的数据、分析结果和设计的算法，将被开发成网络数据库和网络服务器，为社区服务。我们已经在提议的研究中开始了几个子主题，并预见了一些成功。

Algorithm design and analysis plays a central role in computer science. Bioinformatics and computational omics are emerging interdisciplinary areas of study that require expertise from computational sciences and biological sciences. On one hand, biology has become a high-throughput science where its applications are desperate for advanced computing techniques to digest the huge amount of biological data to provide further understandings leading to new biological discoveries. On the other hand, the practice of algorithm design and analysis on the computational problems formulated out of the biological applications helps improve our understandings of the nature of computation which could perhaps trigger new revolutions in computer science. The proposed research, which is driven by large volumes of biological data, has exactly this two-fold significance. The target applications in our proposed research are genome-wide linkage and association studies (GWLAS) using single nucleotide polymorphism (SNP) genotype data, and whole proteome and whole metabolome identification using mass spectral data. On the former, our goal is to build the dense SNP haplotype map to provide finer and deterministic haplotype allelic information for reviving haplotype-based GWLAS. Upon success, we would be able to pass through the seeming bottleneck of the genotype-based GWLAS, particularly to make contributions to the cattle genomic selection programs. On the latter, we aim at designing novel algorithms with proven performance to automate the peptide identification and the metabolite identification for the most effective use of mass spectral data. Upon success, we would be able to use the whole proteome profile for whole genome annotation to detect new genes not expected by current gene prediction tools; we would also be able to use the whole metabolome quantitative profiling to pinpoint effective biomarkers to assist disease diagnosis. Our research results, including curated data, analytical results, and designed algorithms, will be developed into web-databases and web-servers to serve the community. We have started several subtopics in the proposed research, and foreseen a number of successes.