该文主要研究了生物信息学中的几个组合优化问题,涉及到生物信息学中基因组学和蛋白质组学两大研究领域.在基因组学方面,该文研究了单体型装配问题.单体型装配问题就是根据已知的SNP片段求单体型的问题.这方面的工作,文中首先给出了一个最少错误修正问题的整数规划模型,并证明了它的NP-完备性.又用自组织神经网络给出了求解最少错误修正问题的近似算法,模拟结果显示,该算法的计算效果很好.论文还研究了k倍体的单体型装配问题中的最小片段删除模型(k-MFR),证明了当片段是连续的情况下,k-MFR问题是多项式可解的,并给出了片段连续和含有间隙两种情况下的动态规划解法.对于单体型推断问题,即根据基因型推断单体型的问题,论文进行了两方面的研究工作.一方面是将单体型推断问题转化为一个图论问题,并给出了一个贪婪算法,而且,对于带限制的单体型推断问题,也给出了相应的算法.另一方面,该文利用一种新的思路,提出了求解单体型推断问题的树生长算法,这是一个多项式时间的近似算法.在解实际问题时,树生长算法运行效果很好.在蛋白质组学的研究中,该文采用Dill在1985年提出的简化的HP模型.该文在三角网上研究了Hayes提出的蛋白质结构唯一性问题,证明了:1)对任意不小于20的正整数n,存在长度为n的开链或闭链,其最优结构是唯一的.2)存在长度能被18整除的HP链,其最优结构的个数随长度的增长呈指数增长.最后,作为对方格网中Hayes问题证明的一种补充,该文给出了一类特殊的HP链,并证明了这类HP链在平面方格网上具有唯一的最优构形.