随着基因组研究的不断深入，生物信息学这一领域得到了迅速的发展。 本论文就是在生物信息学中的大规模基因组测序中的信息分析和基因组中非编码区信息结构分析两个重要方面开展的一些研究工作。 具体来说是： 1．新的DNA序列拼接算法的研究； 2．Repeat Separation相关理论问题的研究； 3．基于EST序列寻找ncRNA新基因的方法的研究； 4．基于SARS蛋白的siRNA设计。 主要成果有： 针对基因组序列拼接问题提出了新的算法。其实质是将拼接问题抽象成为求解最短公共超串问题，并将局部搜索(Local Search)方法用于求解最短公共超串中。这一新的策略为克服传统的基于贪心算法的拼接软件所导致的拼接错误开辟了途径。本文还进一步提出了“邻域剪枝”(Neighborhood Pruning)和“互补校验”(Complementary-validation)两种优化策略，从提速和提高拼接质量两方面显著地改进了算法性能。 本文将基因组序列拼接中重复序列的处理问题形式化为K-最近子串问题(K-Closest Substring Problem)和K-最小海明距离和子串问题(K-Consensus Pattern Problem)。我们借鉴并发展了“随机维选取策略”(Random sampling strategy)，取得以下研究成果： 1．给出O(1)-最近子串问题的一个PTAS。 2．给出O(1)-最小海明距离和子串问题的一个PTAS。 3．给出了K-最近串问题(Hamming radius K-clustering problem，K-最近子串问题当L=m时的一个特例)的(2—ε)不可近似性的一个新颖直接的证明。 以上研究结果可望为设计解决repeat相关问题的实用算法有所启发。 关于基因组中非编码区信息结构分析的研究当中本文主要包括以下两方面的工作： 建立了基于EST数据库发现新的ncRNA基因的系统方法，并完成了相应的软件。在利用这些软件寻找ncRNA基因的工作中我们发现了9条序列与已知的ncRNA基因高度同源，他们有scRNA、snRNA、snoRNA和SRP RNA；另有一条可能是人的新ncRNA候选序列。由此，表明EST数据库中确实包含ncRNA基因的信息。这一结果也证实了我们的方法是正确的、有效的。 针对SARS冠状病毒(SARS Coronavirus，SARS-CoV)中编码5个主要蛋白质的基因，用生物信息学的方法设计了348条候选siRNA靶位。理论上，相应的siRNA双链体可能会特异性地抑制SARS-CoV靶基因的表达，同时不会影响细胞正常基因。这也为下一步进行实验研究提供了理论基础。