Algorithm design and analysis, and software tool development, in bioinformatics and computational biology

算法设计和分析在计算机科学中起着核心作用。生物信息学和计算生物学是新兴的跨学科研究领域，需要计算科学和生物科学的专业知识。一方面，生物学已经成为一门高通量的科学，其应用程序迫切需要先进的计算技术来消化海量的生物数据，以提供进一步的理解，导致新的生物学发现。另一方面，对生物应用中形成的计算问题进行算法设计和分析的实践有助于提高我们对计算本质的理解，并可能引发计算机科学的新革命。这项研究具有双重意义，我们将重点放在两个生物学应用上：蛋白质核磁共振波谱和全基因组系统发育分析。蛋白质核磁共振波谱是在原子分辨率下确定蛋白质三维结构的两项关键技术之一，为了获得准确的结构，近乎完整的共振序列指认是先决条件。我们在这个项目中的研究重点是自动化光谱数据分析，以确保几乎完整的共振序列分配。一旦成功，我们将能够将目前耗时和昂贵的技术转变为高通量技术。使用全基因组进行系统发育分析的影响是，单个基因可能暗示有争议的进化路径，而整个基因组被认为包含最丰富的进化信息。这一研究的关键是以一种能够高效和有效地进行系统发育分析的方式来表示整个基因组。我们最近提出了一些新的表述，并与他们一起，我们对禽流感病毒的系统发育分析感兴趣，以描绘它们的全球迁移和进化模式。预期结果将有助于快速识别新出现的禽流感病毒，并快速确定疫苗接种策略。

Algorithm design and analysis plays a central role in computer science. Bioinformatics and computational biology 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 understanding of the nature of computation, and perhaps triggers new revolutions in computer science. The proposed research has exactly this two-fold significance, where we focus on two biological applications: protein Nuclear Magnetic Resonance (NMR) spectroscopy and whole genome phylogenetic analysis. Protein NMR spectroscopy is one of the two key technologies that determine protein three dimensional structure at the atomic resolution, where in order to obtain accurate structure a nearly complete resonance sequential assignment is a prerequisite. Our research focus in this project is the automated spectral data analysis to guarantee nearly complete resonance sequential assignments. Upon success, we would be able to transform the currently time-consuming and expensive technology into a high-throughput one. The impacts of phylogenetic analysis using whole genomes are that individual genes might suggest controversial evolutionary pathways and that whole genomes are believed to contain the richest evolutionary information. The key thing in this line of research is to represent whole genomes in a way that the phylogenetic analysis can be efficiently and effectively done. We have recently proposed some new representations, and with them, we are interested in the phylogenetic analysis on avian flu viruses to picture their global migration and evolutionary patterns. The expected results will help in fast identification of emerging avian flu virus and fast determination of vaccination strategies.