基因组学问题的精确算法

本课题主要研究精确算法在基因组学中两个常见问题中的应用：序列比对问题和基因表达及调控分析问题.这两个问题在基因组学中有着重要的应用,但传统的模型和方法缺乏稳定性和精确性,不能够揭示生物过程的内在机理,故组合优化模型是一种新的有效途径.但组合优化模型通常是NP-难问题,并且其近似解在生物学上意义不大,故寻找复杂度低,实际可行的精确算法成为解决此类问题的重关键.本课题以此为出发点,结合这些基因组学中问题本身的结构,利用生物进化保守性以及DNA的三维结构,设计这些问题新的优化模型；然后利用精确算法中新出现的技巧:固定参数化算法和树宽图的概念,设计复杂度低的可以在实际中应用的算法；把得到的算法进一步推广到其他基因组学中的问题上以及组合优化问题上,促进这些问题精确算法的改进；利用得到的算法研究与树宽相关问题的精确算法的理论；根据得到的算法和理论讨论精确算法的下界,从而促进精确算法、其理论和应用的研究

近些年,由于新一代测序技术的发展,使得临床医学基因组学研究成为可能.但是随着海量数据的产生,这使得基因组学问题模型变得更加复杂,算法复杂度更高.模型求解成为解决这些医学问题的瓶颈,和模型结构相结合的算法成为解决此类问题的一个有效途径.本课题集中在基因组学若干问题上,给出其数学模型,给出与模型结合的精确算来求解生物医学中的问题. .本课题经过三年的研究,部分结果已发表,部分结果尚待发表,主要结果包含以下几个方面： 设计了基因表达调节问题的数学模型以及相关的精确算法.在基因表达与调节问题中的结合位点识别问题上,结合DNA的三维结构,给出了一种非常有效的寻找结合位点的方法.相比于已有的方法,此方法可进一步提高结合位点识别的准确度和精度；利用设计的算法,研究基因表达以及基因组学和免疫系统的关系,发现了一个重要的致病基因以及其功能;另一方面,设计了一个整合统计和网络分析的模型,利用精确算法,寻求最小子图,寻找发病基因和疾病的关系,以及基因组和免疫系统的关系.设计了细菌种群和环境因素问题的模型和精确算法.在研究细菌种群的时候,如何正确的判断细菌种群和环境因素之间的关系时问题得核心.由于环境因素众多,这些环境因素可能相互影响,需要用多元分析的方法正确揭示这些关系.我们设计了一个新的多元分析的方法,此方法在研究细菌种群和基因表达的关联性中有着重要的应用.根据所有相关的基因以及相应的环境条件,根据时间节点,组建不同的网络,然后通过寻找这些网络间的相似子图,来发现基因,细菌和环境条件的关系.对于每一个时间节点的网络建立,需要正确计算环境因素和基因的关系.把所设计的模型应用到老年痴呆模型,发现几个特别的基因在老年痴呆病的发作中发挥着重要的应用;把所设计的模型利用到细菌种群数据库上,得到了一系列细菌的共存性和排斥性;所设计的模型用于验证类药物对提高调节性免疫细胞的活性调节上,发现了一种药物的调节作用.设计了序列比对问题的精确算法.对于序列比对问题,把此问题转化为一个Steiner树模型,设计了一个算法,可以估计相对保守性序列的长度,以此为长度作为固定参数,设计了一个精确算法,复杂度大为降低,在理论上得到预期的结果.对于临床医学中的实际问题,结合数据的特点,其提出了树星的概念,指出所有子图都可以转化为一个或者若干树星e,而树星的数目是有限的,故算法求解的空间也非常有限,故很大程度的降低。