资源描述：
《基于序列非比对法的病毒感染特定宿主细胞的可能性评估研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
硕士学位论文基于序列非比对法的病毒感染特定宿主细胞的可能性评估研究作者姓名臧翔学科专业凝聚态物理指导教师刘雪梅副教授所在学院物理与光电学院论文提交日期2018年4月 EvaluationofthePossibilityofVirusInfectionHostCellbySequenceAlignment-FreeStatisticsADissertationSubmittedfortheDegreeofMasterCandidate：XiangZangSupervisor：XueMeiLiuSouthChinaUniversityofTechnologyGuangzhou,China 分类号：O469学校代号：10561学号：201520122306华南理工大学硕士学位论文基于序列非比对法的病毒感染特定宿主细胞的可能性评估研究作者姓名：臧翔指导教师姓名、职称：刘雪梅副教授申请学位级别：理学硕士学科专业名称：凝聚态物理研究方向：生物信息论文提交日期：2018年4月14日论文答辩日期：2018年5月31日学位授予单位：华南理工大学学位授予日期：年月日答辩委员会成员：主席：冯兆庆委员：文德华朱瑞董有忠张向东 华南理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研宄所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：》忧年／月今曰学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：研宄生在校攻读学位期间论文丄作的知识产权单位属华南理工大学。学校有权保存并向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅（除在保密期内的保密论文外）；学校可以公布学位论文的全部或部分内容、缩印或其它复制手段保存、汇编学位论，可以允许采用影印内容相—致文。。本人电子文档的内容和纸质论文的本学位论文属于：：年），（校保密委员会审定为涉密学位吋间＿＿月曰□保密＿月日解密后适丨ｎ木授权书。于年＿＿＿保密同意在校园网上发布，供校内师生和与学校有共享协议的＃，单位浏览；同意将本人学位论文提交中国学术朋刊（光盘版）电子杂志社全文丨，。出版和编入ＣＮＫＩ《中０知识资？原总车》彳专播学位论文的全部或部分内容“”内打Ｖ请在以上相应方框）（日期：作者签名分曰期＞此：厶指导教签名师々 摘要尽管病毒对人类健康及垃圾降解都起着非常重要的作用，但它们很难被研究。科学家不能在实验室培养大多数病毒，且鉴定它们的遗传序列通常很难，因为它们的基因组成小而且进化速度快。随着新一代测序技术的发展，人类得以进一步探知生命的本质和起源，数以百万计的生物学数据库如雨后春笋般的迅速出现和成长，通过深入分析大量生物学数据，可以更好地了解病毒基因组的多样性，以及病毒和它们的宿主细胞及环境之间的相互作用。毒感染宿主细胞的研究对于了解微生物群落的功能和动态具有重要的意义，病毒是依赖于其宿主细胞的分子机制进行复制并产生子代病毒颗粒的。数据表明，病毒与宿主细胞在遗传信息上具有相似的字模式（K-tuple），病毒的DNA序列和其可感染的宿主细胞的DNA序列通过字模式的统计打分值往往比与随机的宿主细胞打分值高，也就是病毒和其可感染的宿主细胞的DNA序列有一定的相似性。对于病毒和宿主细胞之间的相似性，利用K-tuple的频率分布来描述物种的序列特征，这给通过K-tuple算法对微生物聚落进行比较提供了理论依据。对于某个微生物聚落的比对结果，其仅仅以K-tuple的一个频率向量作为表示，而与序列的参考基因没有关系。两序列的比对，也即是通过比较K-tuple的特征向量，得到一个表示两序列距离的打分值，进而比较两序列的相似性或相异性。目前经典的基于K-tuple频率分布的非比对法有Eu、d2star、d2S、Hao和Ch等。本论文使用Eu、d2star、d2S、Hao和Ch这五种非比对算法对病毒识别的优劣性通过ROC曲线和AUC柱状图进行了比较；另外对这五种算法的全局比对和局部比对进行了分析；发现d2star和d2S方法效果优于其他三种方法，更适合于病毒的研究。接下来使用d2star和d2S方法对病毒聚类进行了探讨，发现d2S对病毒的聚类效果优于d2star，最后使用d2star和d2S非比对，对病毒的DNA序列和宿主细胞的DNA序列进行打分，通过该打分值与获得的阈值进行比较，来判断该病毒是否能入侵宿主细胞，进而寻找出探究病毒和宿主细胞关联性的有效方法。基于K-tuple频率分布的序列非比对法来探讨病毒和宿主细胞的相似性目前研究的比较少，通过使用基于K-tuple的非比对法可以加速宏基因组研究并来寻找科学界所未知的病毒。进而成为一个探索地球上病毒的巨大的且未知的多样性的一个新兴工具。关键词：病毒；宿主细胞；d2star非比对法；d2S非比对法；K-tuple；聚类I ABSTRACTAlthoughvirusesplayaveryimportantroleinhumanhealthandwastedegradation,theyaredifficulttostudy.Mostvirusescannotbecultivatedinthelaboratory,andtheirgeneticsequencesareoftendifficulttobeidentifiedbecausetheirgenesaresmallandevolverapidly.Withthedevelopmentofnext-generationsequencingtechnology,humanbeingscanfurtherexplorethenatureandoriginoflife.Millionsofbiologicaldatabaseshavesprungupandgrownuplikemushrooms.Throughin-depthanalysisofalargenumberofbiologicaldata,wecanbetterunderstandthediversityofviralgenomes,aswellastheinteractionbetweenvirusesandtheirhostcellsandenvironment,andthepathogenicityofpathogens.Thestudyofvirusinfectinghostcellsisofgreatimportanceforunderstandingthefunctionanddynamicsofthemicrobialcommunity.Thevirusreliesonthemolecularmechanismsofitshostcellstoreplicateandproduceprogenyvirusparticles.Thedatashowedthatthevirusandhostcellshavesimilarwordpatterns(K-tuple)ingeneticinformation.TheDNAsequenceofthevirusandtheDNAsequenceofitsinjectablehostcellareoftenstatisticallyscoredbyawordpatternhigherthanarandomhostcellscore,indicatingthatthevirushassomesimilaritywiththeDNAsequenceoftheinfectivehostcell.Forthesimilaritybetweenvirusandhostcells,wecancomparetherelationshipbetweenthetwobycomparingthenucleicacidsequencebetweenvirusandhostcell.Therefore,thealignment-freesequencecomparisonmethodbasedonK-tuple'sfrequencydistributionhasgraduallyreachedthestageofhistory.ThefrequencydistributionoftheK-tupleisusedtodescribethesequencecharacteristicsofthespecies,whichprovidesatheoreticalbasisforcomparisonofthemicrobialsettlementsbytheK-tuplealgorithm.Forthealignmentofacolonyofmicroorganisms,itisonlyrepresentedbyafrequencyvectorofK-tuple,butnotrelatedtothereferencegeneofthesequence.ThecomparisonoftwosequencesistogetascorethatrepresentsthedistancebetweentwosequencesbycomparingtheeigenvectorsofK-tuple,andthentocomparethesimilarityordissimilarityofthetwosequences.Thecurrentalignment-freesequencecomparisonmethodbasedonK-tuple'sfrequencydistributionincludeEu,d2star,d2S,Hao,andCh.Inthispaper,fivealignment-freesequencecomparisonmethodincludedEu,d2star,d2S,HaoandCh,areusedtoanalyzevirusrecognition.Firstly,theadvantagesanddisadvantagesofthefiveII algorithmsforvirusidentificationwerecomparedbyROCcurveandAUChistogram.Inaddition,theglobalalignmentandlocalalignmentofthefivealgorithmsareanalyzed.Itisfoundthatthed2starandd2Smethodsarebetterthantheotherthreemethods,whichismoresuitableforvirusresearch.Thend2starandd2Smethodswereusedtoinvestigatethevirusclustering.Itwasfoundthattheclusteringeffectofd2Sontheviruswasbetterthanthatofd2star.Finally,d2starandd2SwereusedtoscoretheDNAsequenceofthevirusandtheDNAsequenceofthehostcell.Bycomparingthescorewiththeobtainedthreshold,itcanbejudgedwhethertheviruscaninvadethehostcell,therebyfindinganeffectivemethodforexploringthecorrelationbetweenthevirusandthehostcell.Discussionofthesimilaritybetweenvirusesandhostcellsbasedonalignment-freesequencecomparisonmethodisrelativelyrare.Theuseofalignment-freesequencecomparisonbasedonK-tuplecanacceleratemetagenomicresearchandsearchforvirusesthatareunknowntothescientificcommunity.ItwillbecomeanewtooltoexplorethehugeandunknowndiversityofvirusesonEarth.Keywords:virus;hostcell;d2star；d2S;K-tuple;clusteringIII 目录摘要..........................................................................................................................................................IABSTRACT............................................................................................................................................II第一章绪论...........................................................................................................................................11.1研究背景和研究意义...................................................................................................................11.2病毒入侵宿主细胞机制的分析方法...........................................................................................21.3基于K-tuple的序列非比对法研究进展.....................................................................................41.4背景序列为马尔科夫链模型的确定...........................................................................................51.5本章小结.......................................................................................................................................6第二章基于K-tuple的序列非比对算法的研究.................................................................................72.1序列比较.......................................................................................................................................72.2序列比对.......................................................................................................................................82.2.1双序列比对法........................................................................................................................82.2.2多序列比对法........................................................................................................................82.3基于K-tuple的序列非比对法的介绍.........................................................................................82.4本论文的研究方案及软件包工具介绍.....................................................................................112.5本章小结.....................................................................................................................................13第三章基于K-tuple非比对法的病毒入侵宿主细胞机制的研究...................................................143.1噬菌体.........................................................................................................................................143.2噬菌体入侵宿主细胞的机制.....................................................................................................153.3实验数据.....................................................................................................................................163.4实验数据的统计显著性.............................................................................................................183.5序列非比对受不同参数的影响.................................................................................................193.5.15种算法对于全局和局部比对的影响...............................................................................193.5.25种算法受不同K-tuple值的影响.....................................................................................213.5.3d2S和d2star算法受马尔科夫阶次的影响.......................................................................233.6本章总结.....................................................................................................................................24第四章用序列非比对法d2S和d2star结合邻接法NJ对病毒进行聚类研究...............................254.1系统树简介.................................................................................................................................254.2系统树的表示方法.....................................................................................................................264.3系统树的类型.............................................................................................................................27IV 4.4本文案例.....................................................................................................................................274.5本章小结.....................................................................................................................................32第五章用序列非比对法d2S和d2star对病毒感染宿主细胞可能性的评估.................................345.1病毒和宿主细胞基因相似性理论.............................................................................................345.2病毒和宿主细胞的序列非比对比较.........................................................................................345.3最佳阈值的确定.........................................................................................................................355.4最佳阈值应用实例.....................................................................................................................365.5本章小结.....................................................................................................................................37第六章总结与展望.............................................................................................................................38参考文献...............................................................................................................................................39附录1....................................................................................................................................................43攻读硕士学位期间取得的研究成果...................................................................................................44致谢.......................................................................................................................................................45V ContentsABSTRACT.............................................................................................................................................IABSTRACT............................................................................................................................................IIChapter1Introduction.............................................................................................................................11.1Researchbackgroundandresearchsignificance...........................................................................11.2Analysismethodofthemechanismofvirusinvadinghostcell....................................................21.3Progressinthestudyofsequencealignment-freemethod............................................................41.4ThedeterminationofMarkovchainmodelofsequencebackground...........................................51.5Chaptersummary..........................................................................................................................6Chapter2ResearchofsequencealignmentfreealgorithmbasedonK-tuple.........................................72.1Comparisonofsequence...............................................................................................................72.2Sequencealignmentmethod..........................................................................................................82.2.1Doublesequencealignment....................................................................................................82.2.2Multiplesequencealignment..................................................................................................82.3IntroductionofalignmentfreemethodbasedonK-tuple..............................................................82.4Theresearchschemeandsoftwarepackagetoolofthispaper....................................................112.5Asummaryofthischapter..........................................................................................................13Chapter3StudyonthemechanismofvirusinvasionofhostcellbasedonK-tuple............................143.1bacteriophage..............................................................................................................................143.2Themechanismofphageinvadinghostcells..............................................................................153.3experimentaldata........................................................................................................................163.4Statisticalsignificanceofexperimentaldata...............................................................................183.5Influenceofdifferentparametersonthesequencealignmentfreemethod.................................193.5.1Theinfluenceofthetotallengthandthelocalalignmentofthesequence...........................193.5.2TheinfluenceofdifferentKvalueson5algorithms............................................................213.5.3TheinfluenceofMarkofforderond2Sandd2staralgorithm..............................................233.6Asummaryofthischapter..........................................................................................................24Chapter4Clusterstudyofvirusbyd2Sandd2starcombinedwithadjacentNJ..................................254.1Abriefintroductionofclustering................................................................................................254.2Therepresentationmethodofclusteringtree..............................................................................264.3Typeofclustertree......................................................................................................................27VI 4.4Thecaseofthisarticle.................................................................................................................274.5Asummaryofthischapter..........................................................................................................32Chapter5Evaluationofthepossibilityofvirusinfectedhostcellswithd2Sandd2star.....................345.1Genesimilaritytheoryofvirusandhostcell...............................................................................345.2Comparisonofthesequenceofvirusandhostcell.....................................................................345.3Determinationofthebestthreshold............................................................................................355.4Anapplicationexampleofthebestthreshold.............................................................................365.5Asummaryofthischapter..........................................................................................................37Chapter6SummaryandProspect.........................................................................................................38Reference...............................................................................................................................................39appendix1.............................................................................................................................................43Researchresultsobtainedduringamaster'sdegree..............................................................................44Thanks...................................................................................................................................................45VII 第一章绪论第一章绪论1.1研究背景和研究意义自上世纪90年代人类基因组计划开展以来，生命科学已经有了快速的发展，并且衍生出了生物信息学这一门学科[1-2]，生物信息学主要是由三大学科组成，分别是生命科学，计算机科学和数学科学。具体来讲它是一门交叉科学，它包含了生物信息的获取、加工、存储、分配、分析、解释等在内的所有方面，它综合运用了数学科学、计算机科学和生物科学等各种工具，来阐明和理解大量生物数据背后所包含的生物学意义。生物序列比对是生物信息学的重要部分之一，其基本思想是将核酸序列或蛋白质一级结构上的序列都看成由基本字符组成的字符串，通常利用两条序列之间的字符差异来测定两序列之间的相似性，两条序列中相应位置的字符如果差异大，那么序列的相似性低，反之序列的相似性就高。通过检测序列之间的相似性，可以发现生物序列中的功能、结构和进化的信息。序列比对的理论基础是进化学说，如果两个序列之间具有足够的相似性，就推测二者可能有共同的进化祖先[3-4]。随着自然科学的发展，现在人们普遍认识到，未知的细菌和古细菌（原核生物）在许多生态系统中主宰了生物的数量，它们控制了重要的生物化学循环，并显著影响人类、动物、农作物的健康[5-6]。然而，关于感染细菌和古细菌的病毒鲜为人知，病毒通常比原核生物的数量要多，估计是地球上最丰富的生物体，他们是限制其宿主细胞数量的重要因素，因此他们可以显著影响原核生物的生命进程和生态系统功能。例如，在海洋环境中，病毒可以每天杀死高达40%的原核生物。病毒是宿主细胞进化的重要介质，在病毒和宿主细胞之间毒力和抗性的“军备竞赛”中，它们对宿主细胞种群施加了很强的选择性压力。病毒也介导了基因水平转移，从而扮演了宿主细胞基因革新的关键媒介。随着新一代测序技术的快速发展，病毒鉴定成为一个非常重要的处理基因组数据必不可少的步骤，特别是对大量基因组数据来说，通过深入分析大量生物学数据，我们可以更好地了解基因组的多样性和动态的病毒，以及病毒和它们的宿主细胞、环境之间的相互作用和病原体的致病性[7-8]。通过测序数据来探究病毒和宿主细胞及环境的关系。通常使用最广泛的病毒鉴定方法有序列搜索，系统发育，长度为N的序列的频率，朴素贝叶斯分类器，支持向量机模型和马尔科夫模型等[9-11]。随着新工具的不断改进，精度也在不断提高。但新一代测序数据产生的读段长度的减少和物种水平识别的准确性显1 华南理工大学硕士学位论文著下降是所有当前算法的共同缺点。因此为提高性能，使用短序列的物种或在子物种水平上进行病毒鉴定。长期的评估病毒多样性的方法已不适用于用宿主细胞培养的新病毒。尽管它也能直接告诉我们病毒可以感染哪些宿主细胞，但隔离的方法是低流量的，这要求目标宿主细胞的强劲增长，这对于许多细菌和古细菌往往是不可能的。因此，病毒分离在采样病毒多样性上大大欠缺，病毒分离株的多样性是高度偏颇的。然而，宏基因组测序和组合而成的病毒群，提供了一个强大的，高通量和平均值去识别新病毒。最近一些针对宏基因组序列的高覆盖深度的研究活动显著增加了采样病毒的多样性。宏基因组学正在迅速扩大研究者在病毒多样性上的视野，由宏基因组装而成的病毒序列的分析工作，并不像病毒分离，不能明显地揭示什么宿主细胞他们可以感染。随着宏基因组数据越来越多，预测这些宏基因衍生的病毒可能会感染哪些宿主细胞的需求变的越来越多。本文所做的工作就是基于在获得大量的病毒和宿主细胞的基因组数据的基础上，通过一系列的统计算法（基于K-tuple的序列非比对法），借助计算机去分析比较病毒和宿主细胞的基因数据，从而分析出它们所代表的生物学意义，以及病毒和宿主细胞之间的关联性，具体来讲就是病毒更容易入侵哪些性质的宿主细胞，从而给我们的科学研究以及病毒疾病的预防治疗工作带来另一个角度的参考意义。1.2病毒入侵宿主细胞机制的分析方法人们普遍认为，细菌和古细菌（原核生物）在许多生态系统中发挥着重要作用，并对人类，动物和植物的健康产生显著影响。然而，对感染原核生物的病毒知之甚少。由于病毒感染可导致宿主细胞裂解，因此病毒通过调节和控制原核生物的数量直接间接地导致病毒学过程。通过对当前主流的病毒－宿主细胞的关系研究发现，病毒经过与宿主细胞的共同进化，能通过改变宿主细胞膜的生化性状侵入宿主细胞，然后通过控制宿主细胞基因表达，从而在宿主细胞内营造一个适合自身生长繁殖的有利环境，而且病毒还能通过调控宿主细胞内基因表达，使宿主细胞合成对自己有益的相关蛋白类物质，以促进自身在宿主细胞内的增值效率等。而这些过程都离不开病毒和宿主细胞的基因调控。因此我们考虑通过对病毒和宿主细胞的基因进行分析，归纳出探究病毒和宿主细胞关联性的有效方法。根据分子序列分析法，最近开发了几种计算方法去辨别哪一种宿主细胞病毒可能感染，这些方法一般分为三大类：（一）使用病毒，宿主细胞基因序列同源性的方法；（二）病毒和宿主细胞共变异分析的方法；（三）序列组成方法。第一组的方法2 第一章绪论依赖于病毒宿主细胞的同源性搜索。根据水平基因的转移，防御系统中使用的短程区域共享，或前病毒使用的整合位点，病毒和宿主细胞可以分享基因或者短序列元素。同源搜索高度依赖于未知病毒的宿主细胞在宿主细胞基因库中是否存在。尽管如此，在特定的序列比较中，和别的方法相比，同源性搜索产生了最高的预测精度（平均水平在22–62%），然而，对于许多新的尚未确定的病毒，其潜在宿主细胞的同源性可能受到严重限制，如果它们相关宿主细胞的基因组还没有被测序。使用新一代测序数据从环境样品中回收微生物遗传物质的宏基因组测序可以用于细菌，古细菌和病毒的高通量鉴定，无论其可培养性如何。通过从各种环境（包括人类肠道[12-13]，海洋[14-15]和土壤[16]组装短读段发现了越来越多的新病毒，它们的生物功能和原核宿主细胞不能从宏基因组数据中直接推断出来。最近已经开发了一些计算方法用于预测给定病毒序列的宿主细胞。最直接的方法是基于比对的基因同源性搜索和病毒与宿主细胞基因组之间的搜索[17]。但是，没有多少病毒与宿主细胞共享区域，而没有多少宿主细胞具有间隔区。相反，序列非比对法对于揭示病毒与宿主细胞的相互作用关系是非常有效的，因为观察到病毒与宿主细胞具有高度相似的K-tuple用法，可能会导致病毒复制依赖于宿主细胞翻译机制。Edwards等人[18]和Roux等人[19]使用基于欧氏距离和曼哈顿距离来测量病毒和宿主细胞之间的距离，并将宿主细胞预测为与查询病毒距离最小的宿主细胞。Ahlgren等人[20]对宿主细胞预测的各种K-tuple长度上的序列非比对差异度量进行了综合评估。该研究评估了十一种差异度度量，其中包括基于观察到的词频如欧氏距离和曼哈顿距离以及基于标准化词频如d2star和d2S的那些度量。对于感染宿主细胞的病毒来说，其DNA结构简单，序列相对较短。因此，参与病毒翻译蛋白质的编码基因也相对较短。因此，K-tuple的选取也应该与病毒的DNA结构相适应。进一步分析指出，对病毒这类小分子物质，其编码基因的特征编码区之间关联性较弱，这点可从不同的马尔科夫参数选择得到体现。因此，在兼顾算法时空复杂度、资源利用效率的情况下，可直接使用低阶甚至1阶马尔科夫模型就能达到预期效果。基于以上的研究，本论文中我们选取了200个已知可以入侵宿主细胞的病毒（NCBI得到），和200个未知可否入侵宿主细胞的病毒作为研究对象，使用基于K-tuple频率分布的各种非比对法获得的距离在不同K-tuple值上进行了评估，由此来预测病毒宿主细胞的相互作用。3 华南理工大学硕士学位论文1.3基于K-tuple的序列非比对法研究进展分子序列比较是计算生物学中最基本的问题之一，分子序列比较最广泛使用的方法是基于序列比对，包括Smith-Waterman算法[21]，BLAST[22-23]等。随着新一代测序技术的发展，研究者们可低成本的获得海量的读段数据，而如何处理这些海量的数据并从中提取生物学知识则显得至关重要。通常对这些数据进行处理的手段是分子序列比较，由于基因组的随机分布，基因组的某些部分可能测序不到，特别是当覆盖率相对较低时，即使可以将读段组装成重叠群，这些重叠群可能不会共享长的同源物区域进而使得用序列比对法研究基因组间的关系成为具有挑战性的问题；另外序列比对方法对许多大型基因组和宏基因组数据集测序太耗时。对这些情况，序列非比对法提供了有希望的替代方法。用于基因组比较的序列非比对方法可以分成几个不同类型：a）字频（K-tuple）的统计[24-28]；b）平均最长公共子串[29]，最短子串[30]或两者的组合；c）基于混沌理论的序列表示[31]；d）核苷酸位置[32]；e）傅里叶变换[33]，f）信息论[34]，和g）迭代映射[35]。目前我们可以获得许多有关序列非比对比较方法的优秀综述[36-38]，研究结果表明序列非比对法比基于比对方法更稳健，特别是对基因重排和水平基因转移。在序列非比对比较方法中，基于字频统计的非比对方法易于适应新一代测序数据而最受欢迎。近年来已经开发了许多基于字频的序列非比对法，序列非比对法主要是基于基因片段中字频的统计方法，K-tuple是一段连续的字符片段，长度为K，通过统计K-tuple在两条比对序列中出现的次数，并用统计打分值来判断两条序列的相似度或者相异度。在生物信息学中，我们利用K-tuple的频率分布来描述物种的序列特征，直接使用所观察到的字频来计算序列之间的相异度。这些算法包括Euclidian距离，Manhattan距离，Hamming距离及Jaccard相似系数，d2，FFP[39]，JS[40]。但对构建系统树来说，这些算法效果并不好，其原因在于由简单计数构造的非比对算法包含着突变所导致的与物种分化关系不大的贡献，为了突出物种特异性，必须设法减除掉突变造成的背景噪声，可以采用K-2阶的马尔科夫模型来扣除背景噪声，这些算法有d2S和d2star及他们的推广式，Hao，Teeling[41]，EuF[42]，及Willner[43]等。由于字频通常在不同的基因组区域是稳定的，所以即使序列来自基因组的不同区域，非比对方法也可以很好地工作。在各种非比对算法中，使用归一化K-tuple计数的d2S和d2star已被证明在比较基因组序列方面具有卓越的性能。Wan等人[19]研究了d2S和d2star非比对算法的理论统计特性。Song等人[18]将d2S和d2star的应用从长基因组序列数据扩展到基于NGSreads数据，并且从理论上4 第一章绪论研究了这些非比对算法的性能。Ren等人[16]基于NGSreads数据使用d2S和d2star在不同的马尔科夫模型下测序了28种脊椎动物物种的聚类基因组序列，使用适当的马尔科夫链与使用d2S和d2star获得的相异性得分高度相关（Spearman等级相关系数0.92），另外与d2star相比，d2S受马尔科夫模型的阶次影响较小，例如在独立等同分布模型下，使用d2S的Spearman等级相关系数是0.86。Ragan等人[44]对使用寡核苷酸模式研究16S序列之间关系的早期研究给予了很好的回顾，并比较了使用多序列比对，非比对算法SAB和新开发的d2S得到树状图，结果表明，基于d2S构建的K为6到16的系统树获得了与使用多序列比对的最大似然树最一致的树状图。Chan等人[45]使用4156个核苷酸序列的序列非比对测量进行系统发生推断，使用d2S获得的拓扑结构与使用多序列比对推断的系统发育最为一致，并与基于多序列比对构建的系统树进行比较，尽管存在一些不一致的情况，聚类结果一般与经典系统树具有高度相似的结构。1.4背景序列为马尔科夫链模型的确定使用K-tuple的序列非比对法通常计算基因组序列中长度为K的词的出现频数，并使用基于K-tuple频率定义的非比对算法来比较序列。这些方法可以大致分为两类：需要背景词频的非比对算法和不需要背景词频的非比对算法。Lu等人[28]开发了一个一站式平台，用于计算一套28种不同的非比对方法，并提供各种形式的可视化工具，包括树状图，热图，主坐标分析和网络显示。对于不需要背景词频率的测量，观察到的词频或词语存在（或不存在）直接用于计算不相似度量。这些测量包括但不限于Euclidian距离（Eu），曼哈顿距离（Ma），d2，特征频率分布（FFP），Jensen-Shannon散度（JS）[40]，汉明距离，和Jaccard指数。对于考虑背景词频的非比对法，使用归一化词频计算序列之间的差异性，其中使用背景模型估计的预期词频从观察词频中减去以消除背景噪声和增强信号。这组非比对法包括d2star和d2S[11,10]及其变体[26，27，46]，CVTree[47]，Teeling[41]，EuF[42]和Willner[43]，其中不同形式的序列背景模型被合并。第二组测量要求了解背景序列中字数的近似分布。马尔科夫链广泛用于模拟基因组序列[48]，其中包括许多应用，包括研究碱基之间的依赖关系，某些字型的富集和消耗[49]，长字型出现的预测模式[50-51]以及内含子[52]中信号的检测。马尔科夫链模型的定义特征是“无记忆”属性，这意味着序列的未来状态可以完全根据其最新历史很好地预测，而无需了解整个历史。特别地，r阶马尔科夫链假定未来状态的分布仅依赖于过去r个位置的状态5 华南理工大学硕士学位论文而不管先前的历史，即P（Xt|X1...Xt-1）=P（Xt|Xt-r...Xt-1），其中X1，X2，...Xt是序列X中的状态，Xi取自大小为L的有限字母表中的值。对于DNA序列，字母集是A={A，C，G，T}。马尔科夫链可以以Lr×L矩阵的形式表示，其中矩阵中的元素对应于转移概率P（w|w1w2...wr），w∈A.0阶马尔科夫链是最简单的案件；在这种情况下，序列中的位置是独立的且分布相同的（i.i.d.）。1.5本章小结人类在揭示生命的奥秘方面从未停止过探索的脚步，生物研究所产生不同类型数据的出现和需要，使得分子生物学领域研究如火如荼。核糖核酸和蛋白质的分子序列和结构数据、基因表达谱或微阵列数据，以及代谢途径的数据是分子生物学分析中数据的主要类型。那么，这些海量基因序列数据背后包含什么信息?各生物之间有什么关系?无数问题都亟需人们来解决和回答。面对海量的基因数据，人们不禁想到利用数学、计算机结合生物方法进行处理和研究，由此诞生了一门新的学科——生物信息学。它结合了计算机快捷的计算能力和强大的数据分析能力，使人们从海量基因序列数据中获得生命的奥秘成为可能。目前，生物信息学中基于序列比对基础上的一种算法，—种快速而准确的序列非比对算法越来越受到重视，生物序列分析的非比对方法作为对传统方法的补充和发展已逐渐成为生物信息学中的一个热点。地球上已知的微生物数量庞大，种类多样。长久以来，微生物对人类生产生活产生了多面影响，而部分微生物自身在极端条件下的生存能力，也深深吸引着科学家们不断探索的步伐，但仅局限于通过生物、化学、分子生物学的方法进行研究，目前国内外均鲜有利用序列比对和非比对方法，进行病毒与宿主细胞关联性的研究。我们将考虑将生物信息学中的序列非比对比较法应用到微生物的研究中来，旨在使用序列非比对法来填补该领域的空白。本文分为四部分，其中第一部分简述了序列非比对比较法研究病毒和宿主细胞的关联性的背景和意义，以及序列非比对的基础知识等，第二部分是五种非比对算法对病毒和宿主细胞关联性的优劣性比较分析，第三部分是使用d2S和d2star非比对算法对36种病毒的聚类效果分析；最后第四部分利用d2S和d2star打分阈值对病毒和宿主细胞的关联性进行评估。6 第二章基于K-tuple的序列非比对算法的研究第二章基于K-tuple的序列非比对算法的研究2.1序列比较序列比较是生物信息学中最基本、最重要的操作，通过序列比较可以发现生物序列中的功能、结构和进化的信息。序列比较的根本任务是：通过比较生物分子序列，发现它们的相似性，找出序列之间共同的区域，同时辨别序列之间的差异。在分子生物学中，DNA或蛋白质的相似性是多方面的，可能是核酸或氨基酸序列的相似，可能是结构的相似，也可能是功能的相似。研究序列相似性的目的之一是，通过相似的序列得到相似的结构或相似的功能。通过比较未知序列与已知序列（尤其是功能和结构已知的序列）之间的相似性，可以很容易地预测未知序列的功能。一般来说，相似性很高的两条序列往往具有同源关系，但也有例外，即两条序列的相似性很高，但它们可能并不是同源序列，这两条序列的相似性可能是由随机因素所产生的，这在进化上称为趋同。直系同源序列是来自于不同种属的同源序列，而并系同源序列则是来自于同一种属的序列，它是由进化过程中的序列复制而产生的。图2-1序列比较分类7 华南理工大学硕士学位论文2.2序列比对目前序列比较法主要有序列比对和序列非比对两种方法，如图2-1，所谓序列比对,是序列相似性分析的常用方法，又称序列联配。通过将两个或多个核酸序列或者蛋白质序列进行比对，显示其中相似的结构区域，通过比较未知和已知序列的一致性或相似性，可以预测未知序列功能。序列比对又可以分为全局比对，即对序列从头到尾进行比较，试图尽可能多的字符在同一序列中匹配，适用于相似度较高且长度相近的序列，比如Needleman-Wunsch算法；局部比对，是寻找序列中相似度最高的区域，也就是匹配密度最高的部分，适用于在某些部分相似度较高，而其他部位差异较大的序列，比如Smith-Waterman算法。局部相似性比对的生物学基础是蛋白质功能位点往往由较短的序列片段组成的，这些部位的序列具有相当大的保守性，尽管在序列的其他部位可能有插入、删除或突变。此时，局部相似性比对比全局比对具有更高的灵敏度，其结果更具有生物学意义。2.2.1双序列比对法双序列比对是比较两条序列之间的相似区域和保守位点，寻找二者之间可能的进化关系。序列两两比对分析是最简单、最基本的对齐分析。分为三种方法：动态规划法，点阵分析法和词或K串法。2.2.2多序列比对法多序列比对是把两条以上可能有系统进化关系的序列（相似度不一定很高）进行比对的方法。相同或者相似的氨基酸或者核苷酸排列在同一列上，这些对齐的残基在进化意义上是同源的：来自共同的祖先。多序列比对中的全局比对包括动态规划算法、累进法、迭代法、遗传法等；而局部比对分概形分析和区块分析两种方法。2.3基于K-tuple的序列非比对法的介绍生物技术的飞速发展使得生物序列数据急剧增长，可供人们研究的全基因组序列也越来越多。然而由于生物序列比对方法计算量较大，打分函数又带有一定的主观性，同时全基因组序列又比较长，所以利用比对方法来直接分析这些序列是比较困难，因此现8 第二章基于K-tuple的序列非比对算法的研究在人们致力于寻找一些新的方法来进行生物序列尤其是全基因组序列的比较分析，通常把这些方法统称为非比对方法。这种建立在序列比对法基础上的序列非比对算法越来越受到重视。生物序列分析的非比对方法作为对传统方法的补充和发展，由于其快速而准确的特点已逐渐成为生物信息学研究的一个热点。非比对方法也被用来研究基因组进化关系，对于不同的生物，他们有些核苷酸在基因组序列中出现次数的频率是高度稳定的，可以认为他们有可能是亲缘关系的物种，一些调查文献中扩展核苷酸为字（K-tuple），从而通过研究字在序列中出现次数的频率来研究不同生物体间的演化关系，这些方法的主要原理是，前景序列中含有模体，由此推测字（K-tuple）在前景序列中出现的频率高于背景序列，信号比较强。序列非比对法主要是基于基因片段字频率（K-tuple）的统计方法，K-tuple是一段连续的字符片段，长度为K，通过统计K-tuple在两条要比对的序列中出现的次数，并用统计打分值来判断两条序列的相似度。具体如下：在生物分子信息处理过程中，一般将生物分子序列抽象为字符串，序列中的字符取自特定的字母表A，字母表是一组符号或字符，字母表中的元素组成序列。在DNA序列中，4个字符的字母表可以表示为A∈{A，C，G，T}。D2[53]统计可以按如下描述，假设有两条序列A'=A1A2…An及B'=B1B2…Bn，序列长度n相同，组成序列的字母来源于有限的字母表A，大小为d．设w=ww...w，w为DNA序列中所有可能的K-tuple12K组成的集合，p=pp...p为对应的概率。X为w在序列A'中出现的次数，ww1w2wKwY为w在序列B'中出现的次数，令wX%X-(n-K+1)pwww（2-1）Y=Y-(n-K+1)p%www（2-2）则定义统计值D2如下:D2wΑKXYww（2-3）对应的相异度为1D2d212X2Y2wΑKwwΑKw（2-4）9 华南理工大学硕士学位论文统计值D2被认为受背景序列的噪声效应的影响比较大，在D2基础上sun[53]等发展两种推广式D2S和D2star及其相异度d2S和d2star，其范围在0到1之间，定义如下：XY%%D2starwwwΑK(n-K+1)pw（2-5）1n-K+1D2stard2star12X/p%2Y/p%2wΑKwwwΑKww（2-6）XY%%wwD2SKwΑ%2%2X+Yww（2-7）1D2Sd2S12X/X+Y%2%2%2Y/X+Y%2%2%2wΑKwwwwΑKwww（2-8）另外介绍三种经典的非比对算法，Hao，Eu及Ch。4K4KABXY令n=Xi=1AX,i和n=Yi=1BY,i,f=X,f=Y则其他三种非比对如下nnXY定义：K4ffX,iY,i-1-11i=1E[f|MX,iK-2]E[f|MY,iK-2]Hao=1-2224K4KffX,iY,i-1-1i=1E[f|MX,iK-2]i=1E[f|MY,iK-2]（2-9）K1/242Eu(f,f)=XYf-fX,iY,ii=1（2-10）Ch(f,f)XYmax1i4Kf-fX,iY,i（2-11）10 第二章基于K-tuple的序列非比对算法的研究2.4本论文的研究方案及软件包工具介绍序列比对被广泛用于研究分子序列之间的关系。序列比对包括全局比对和局部比对。随着以序列为基础的工具的出现如Blast、序列数据库、RefSeq等方法，尽管它们已经被广泛应用，以序列为基础的方法在某些情况下是不合适的。首先，基因调控区域通常不是高度保守的，使基于序列的方法难以识别相似转录因子的影响的相关的调控区域。图2-2研究方案示意图11 华南理工大学硕士学位论文第二，新一代测序技术产生了大量的短读序列，这对于将它们组装起来用于基因和宏基因组的学习是个挑战。没有跨越许多样本的长的重叠群的情况下，这对于以序列为基础的方法去比较基因和宏基因组是个挑战。第三，病毒更容易传染具有相似的子模块使用模式的病毒宿主细胞，因此，可以推断病毒的宿主细胞也是用相似的子模块。然而，序列比对法通常不适用于研究病毒宿主细胞的传染关系。序列非比对法作为研究序列间关系的有很强优越性的替代方法，因为在实际应用中，基于对齐的方法不合适或太耗时。在这里我们关注于使用了K-tuple的序列非比对算法。这些方法将每个序列映射为K长度的特征向量，这里序列信息被转换为数值例如K-tuple频率。我们基于研究病毒和宿主细胞的相似性，设计了如图2-2[3]研究方案，本论文的研究方案采用由模型到算法到可视的技术路线进行研究。通过统计被比对序列间的K-tuple的频次，用这些频次构成一个对应的向量，不同的序列就对应不同的向量，我们用非比对算法来计算向量之间的距离。n条序列两两比对会产生一个n×n的矩阵，利用这个距离矩阵我们可以用UPGMA或者NJ法画出树状图、网状图、及聚类图等。图2-3多序列比对运行界面另外本研究小组自行开发了多序列比对软件包CaldistancePro，截面图如图2-3，具有计算速度快，简洁，占用空间小的特点。其用于计算序列之间的相异度，实现方法基于K-tuple向量的统计，可以用7种不同的非比对算法计算出多序列之间的相异度，获12 第二章基于K-tuple的序列非比对算法的研究得多序列距离矩阵。主要功能如下：1)能动态设置K-tuple大小K值和马尔科夫阶次Morder值并计算不同K与Morder值下的距离矩阵。2)能实现一对多和多对多的序列比较。3)能设置不同的方法进行序列比较，包括Eu（Euclidian距离），Ma（Manhattan距离），Ch（Chebyshev），d2，Hao（也叫CVTree），d2S及d2star等算法。2.5本章小结序列比对指两个或多个序列按字母比较，尽可能确切地反映它们之间的相似和相异性，用于阐明序列之间的同源关系。序列比对又可以分为双序列比对和多序列比对法，双序列比对一般可以分为三类分别为：动态规划的优化方法，启发式算法和大型数据库搜索设计的概率方法。而多序列比对的常用算法有累进算法、隐马尔科夫模型、迭代比对法等。随着时代的发展，又渐渐衍生出了更加高级的算法，序列非比对算法，它是基于序列比对基础上的一种快速而准确的算法。序列非比对法主要是基于基因片段字频率（K-tuple）的统计方法，按照不同的数学统计方式，序列非比对法又可分为Eu，Hao，d2S，d2star等统计算法，对非比对算法，我们设计了用于研究病毒和宿主细胞的关联性的思路，及我们自行研发出用来多序列比对的软件包，该软件包可用于Eu，Hao，d2S，d2star这五种算法的多序列比对进而获得两两距离矩阵。13 华南理工大学硕士学位论文第三章基于K-tuple非比对法的病毒入侵宿主细胞机制的研究3.1噬菌体图3-1噬菌体结构图噬菌体能够杀死细菌的现象是在1915年由弗德里克·特沃特发现的。1915年8月加拿大医学细菌学家费利克斯·德赫雷尔也发现了这种病毒并把这些病毒称为噬菌体。噬菌体是一类病毒，原指细菌病毒，近年来发现了真菌、藻类都有噬菌体。噬菌体是感染细菌，真菌、藻类、放线菌或螺旋体等微生物的病毒的总称，因部分能引起宿主细胞菌的裂解，故称为噬菌体。本世纪初在葡萄球菌和志贺菌中首先发现。作为病毒的一种，噬菌体具有病毒的一些特性：个体微小；不具有完整细胞结构；只含有单一核酸。可视为一种“捕食”细菌的生物。噬菌体基因组含有许多个基因，但所有已知的噬菌体都是细菌细胞中利用细菌的核糖体、蛋白质合成时所需的各种因子、各种氨基酸和能量产生系统来实现其自身的生长和增殖。一旦离开了宿主细胞，噬菌体既不能生长，也不能复制。噬菌体是病毒的一种，其特别之处是专以细菌为宿主细胞，常见的噬菌体是以大肠杆菌为寄主的T2噬菌体。如图3-1[5]，跟别的病毒一样，噬菌体只是一团由蛋白质外壳包裹的遗传物质，大部分噬菌体还长有“尾巴”，用来将遗传物质注入宿主细胞体内。噬菌体是一种普遍存在的生物体，而且其周围通常都伴随着细菌。通常在一些充满细菌群落的地方，如：泥土、动物的内脏里，都可以找到噬菌体的踪影。目前世上蕴含噬菌体最丰富的地方就是海水。噬菌体主要由蛋白质外壳和核酸组成，所以，可以根据蛋白14 第三章基于K-tuple非比对法的病毒入侵宿主细胞机制的研究质外壳或核酸的结构特点对噬菌体进行分类。根据蛋白质结构分类可以分为三类，第一类无尾部结构的二十面体，一般这种噬菌体是一个二十面体，外表由排列的蛋白亚单位——衣壳组成，核酸则被包裹在内部。第二类是由有尾部结构的二十面体，一般这种噬菌体除了一个二十面体的头部外，还有由一个中空的针状结构及外鞘组成的尾部，以及尾丝和尾针组成的基部。第三类是线状体，这种噬菌体呈线状，没有明显的头部结构，而是由壳粒组成的盘旋状结构。3.2噬菌体入侵宿主细胞的机制噬菌体颗粒感染一个细菌细胞后可迅速生成几百个子代噬菌体颗粒，每个子代颗粒又可感染细菌细胞，再生成几百个子代噬菌体颗粒。如此重复只需4次，一个噬菌体颗粒便可使几十亿个细菌感染而死亡。当把细菌涂布在培养基上，长成一层菌苔时，一个噬菌体感染其中一个细菌时，便会同上面所说的那样，把该细菌周围的成千上万个细菌感染致死，在培养基的菌苔上出现一个由于细菌被噬菌体裂解后造成的空斑，这便称为噬菌斑。除了一些噬菌体能使宿主细胞裂解死亡外，还有一些噬菌体感染细菌后，并不使细胞死亡，称为溶原性噬菌体，这些噬菌体感染细菌后，将其自身的基因组整合进宿主细胞的基因组，此时，这种宿主细胞称为溶原性细菌。溶原性细菌内存在的整套噬菌体DNA基因组称为原噬菌体，溶原性细菌不会产生许多子噬菌体颗粒，也不会裂解；但当条件改变使溶原周期终止时，宿主细胞就会因原噬菌体的增殖而裂解死亡，释放出许多子代噬菌体颗粒。图3-2噬菌体入侵大肠杆菌示意图15 华南理工大学硕士学位论文如图3-2[5]，一个典型的噬菌体浸染细菌的过程，可以分为三个阶段：感染阶段、增殖阶段和成熟阶段。在感染阶段，噬菌体感染寄主细胞的第一步是“吸附”，即噬菌体的尾部附着在细菌的细胞壁上，然后进行“侵入”。噬菌体先通过溶菌酶的作用在细菌的细胞壁上打开一个缺口，尾鞘像肌动球蛋白的作用一样收缩，露出尾轴，伸入细胞壁内，如同注射器的注射动作，噬菌体只把头部的DNA注入细菌的细胞内，其蛋白质外壳留在壁外，不参与增殖过程。第二阶段是增殖阶段，在噬菌体DNA进入细菌细胞后，会引起一系列的变化，细菌的DNA合成停止，酶的合成也受到阻抑，噬菌体逐渐控制了细胞的代谢。噬菌体巧妙地利用宿主细胞的酶和其它物质，大量地复制子代噬菌体的DNA和蛋白质，并形成完整的噬菌体颗粒。噬菌体的形成是借助于细菌细胞的代谢机构，由本身的核酸物质操纵的。据观察，当噬菌体侵入细菌细胞后，细菌的细胞质里很快便充满了DNA细丝，十分钟左右开始出现完整的多角形头部结构。噬菌体成熟时，这些DNA高分子聚缩成多角体，头部蛋白质通过排列和结晶过程，把多角形DNA聚缩体包围，然后头部和尾部相互吻合，组装成一个完整的子代噬菌体。第三阶段是成熟阶段，即噬菌体成熟后，在潜伏后期，溶解宿主细胞壁的溶菌酶逐渐增加，促使细胞裂解，从而释放出子代噬菌体。在光学显微镜下观察培养的感染细胞，可以直接看到细胞的裂解现象。T2噬菌体在37℃下大约只需四十分钟就可以产生100～300个子代噬菌体。子代噬菌体释放出来后，又去入侵别的宿主细胞，产生子二代噬菌体。综上所述，噬菌体在入侵宿主细胞的过程中，噬菌体DNA在宿主细胞体内的复制增殖是最为关键的环节，对噬菌体的繁殖起到了最为关键的作用。而噬菌体DNA所需的物质来源正是宿主细胞合成其自身DNA所需的物质，那由此就引发了本文的猜想，是不是宿主细胞的DNA与噬菌体的DNA成分越相似，噬菌体越容易入侵宿主细胞，是不是噬菌体入侵数量最多的宿主细胞，它们之间的DNA越相似。这些都是我们要探索的问题。3.3实验数据在序列非比对法的基础上，我们根据病毒和宿主细胞的序列特点对其进行一定优化和调整。生物学中的K-tuple，是指长度为K的一小段基因序列。通过测序方法，利用K-tuple获取其在被测物种全序列中的散布情况，从而得到一个K-tuple基因序列的频率16 第三章基于K-tuple非比对法的病毒入侵宿主细胞机制的研究分布，这一小段基因序列在被测物种全序列中的分布组成表征该物种全序列的特征向量。表3-1200种能入侵宿主细胞的噬菌体部分数据表表3-2200种未知能否入侵宿主细胞的噬菌体部分数据表因此，两序列的比对可通过比较K-tuple的特征向量得到。病毒能通过多种方式着床到宿主细胞上，并能与宿主细胞表面的受体氨基酸链进行信息交换和传递，从而改变宿主细胞的生化结构，使病毒能成功突破阻碍，进入到宿主细胞内。而这一过程和病毒与宿主细胞的基因表达紧密联系。为了从遗传分子层面探究病毒和宿主细胞的关联性，我们从基因库中选取一个宿主细胞的DNA基因序列，然后选取200个已知能感染该宿17 华南理工大学硕士学位论文主细胞的病毒，如表3-1；同时我们选取了200个未知能否入侵宿主细胞的病毒如表3-2。宿主细胞:NZ_CP009494.1host。说明：未知的病毒（但是真实的病毒），类似于200种背景序列，知道能侵入宿主细胞的病毒，相当于200种前景序列。我们用200种未知能否入侵宿主细胞的病毒跟宿主细胞比较，获得200个距离。用200个已知能感染该宿主细胞的病毒和宿主细胞比较，获得200个距离。使用的多序列比对方法是我们组开发的软件包CaldistancePro获得距离矩阵，通过ROC曲线来探讨Eu，Hao，Ch，d2S，d2star这五种方法的优劣性。3.4实验数据的统计显著性任何一个比对，我们都可以计算一个打分值，但重要的是需要判定这个打分值是否足够高，是否能够提供进化同源性的证据。在解决这一问题时，对于偶然出现的最高分，有些思想很有帮助，但是没有一个数学理论能够描述全程比对的分值分布，其中一个能评估其重要性的方法就是将所得的比对打分值和那些同样长度和组成的随机序列进行比较。更普遍更一般的分布的应用可能会夸大它的重要性，把一个已知的比对分值S同预期的分布相关联可能会计算出P值，从而给出这个分值的比对显著性的可能性。通常，P值越趋近于零，分值越有意义。我们使用了五种算法计算了200种已知可入侵的病毒和200种未知的病毒分别和宿主细胞打分，并对两种样品进行了t检验，其p值如下表3-3。表3-3不同K值下，不同距离方法的t检验的p值列表在我们的研究当中，除了使用AUC曲线去证明前景序列与背景序列有明显区别之外，我们还用了t-检验去辅助证明positive病毒（已知能入侵宿主细胞的病毒）的算法18 第三章基于K-tuple非比对法的病毒入侵宿主细胞机制的研究平均距离与negative病毒（未知能否入侵宿主细胞的病毒）的算法平均距离是有明显差异的，t-检验的p值越小证明差异越显著，从上表3-3我们可以看出，无论K值如何变化，所有算法的p值都是非常小的几乎为零，进一步证明了positive病毒与negative病毒的差异是非常显著的，我们所选取的序列是合理的。3.5序列非比对受不同参数的影响ROC曲线又称为受试者工作特征曲线，最初用于评价雷达性能，又称为接收者操作特性曲线，ROC曲线是根据每个值的检测结果作为可能的诊断阈值，从而计算出相应的敏感性和特异性。ROC曲线是根据一系列不同的二分类方法（分界值或决定阈），以真阳性率（灵敏度）为纵坐标，假阳性率（1-特异性）作为横坐标绘制的曲线，曲线下面积的大小（AUC）可以用作衡量诊断测试，范围从0.5到1。它将灵敏度与特异性以图示方法结合在一起，可准确反映统计方法特异性和敏感性的关系，是试验准确性的综合代表。通过ROC曲线可选择最佳的诊断界限值。在这里我们假设灵敏度和特异度的重要程度相同，这样ROC曲线越靠近左上角，试验的准确性就越高。最靠近左上角的ROC曲线的点是错误最少的最佳阈值，其假阳性和假阴性的总数最少。3.5.15种算法对于全局和局部比对的影响AUC在不同序列长度下的分布K=5Morder=110.90.80.70.60.50.40.30.20.1010%20%30%40%50%60%70%80%90%100%d2Sd2starHaoChEu图3-3-a五种算法不同序列长度在不同长度下的AUC比较19 华南理工大学硕士学位论文如图3-3-a，我们分析了五种算法的全局比对（100%）和局部比对（10%-90%）。对前景序列和背景序列，我们的原长为100%，然后分别选取前景序列和背景序列的百分之10%，20%，30%，40%，50%，60%，70%，80%，90%，100%进行比对，上下选取的位置一致，长度一样。选取参数K-tuple的大小为5，d2S、d2star、Hao三种算法的马尔科夫阶次为1，Eu和Ch的马尔科夫阶次为0；从图中可以看到五种算法的整体AUC都非常高，且在不同的长度下其值都比较稳定。我们会发现整体来说（10%的情况下略有差距），对不同长度的局部比对和全局比对影响不大，整体保持稳定状态，性能比较稳定。也就是这五种算法对局部比对和全局比对都相对比较稳定。d2S10.80.60.40.2010%20%30%40%50%60%70%80%90%100%k=4k=5k=6k=7k=8k=9k=10图3-3-bd2S不同序列长度在不同K值下的AUC值d2star10.80.60.40.2010%20%30%40%50%60%70%80%90%100%k=4k=5k=6k=7k=8k=9k=10图3-3-cd2star不同序列长度在不同K值下的AUC值20 第三章基于K-tuple非比对法的病毒入侵宿主细胞机制的研究如图3-3-b和图3-3-c，我们分析了d2S和d2star在不同的K-tuple和相同的马尔科夫阶次（Morder）下，其中我们选取参数Morder=1算出其AUC值，我们会发现不同K值，不同的序列长度，其AUC整体效果都很好，而且比较稳定，也就是说d2S和d2star在不同K值的全局比对和局部比对其性能比较稳定，适合于病毒和宿主细胞的研究。3.5.25种算法受不同K-tuple值的影响接下来我们研究了5种不同算法在马尔科夫阶次（Morder）为1（Eu和Ch的马尔科夫阶次为0）下的ROC曲线，我们选择K=4，5，6，7，8，9,10。如图3-4-a到3-4-g。图3-4-aK=4五种算法下的ROC曲线图3-4-bK=5五种算法下的ROC曲线图3-4-cK=6五种算法下的ROC曲线图3-4-dK=7五种算法下的ROC曲线21 华南理工大学硕士学位论文图3-4-eK=8五种算法下的ROC曲线图3-4-fK=9五种算法下的ROC曲线图3-4-gK=10五种算法下的ROC曲线取K-tuple长度分别为4、5、6、7、8、9、10，对五种非比对法Ch、d2S、d2star、Eu、Hao进行ROC曲线分析，得到图3-4-a至图3-4-g。表征两序列相似程度的特征统计量是通过K-tuple在两序列间的向量距离来描述的，综合来看，当K=4和K=5时评价两序列相似程度的特征统计量Ch、d2S、d2star、Eu、Hao均表现良好；各统计量均能较好的表征两序列相似程度，而且K=5较K=4时各统计量的效果均得到了提升。当K=6时，如图3-4-c所示。Ch值有所下降，说明在K=6时，通过两序列的差异性判断序列相似程度的方法不及其他方法，其他几个统计值变化不大；值得注意的是，Hao特征量在这5种特种统计量的表现仅次于d2S，因此我们判断，K-tuple的长度可能和该类病22 第三章基于K-tuple非比对法的病毒入侵宿主细胞机制的研究毒和宿主细胞的关键单元结构长度吻合，这可能是由于病毒的遗传分子链普遍较短。K-tuple的长度为7时，如图3-4-d所示。Ch统计量还是下降，Hao特征量大幅下滑，表现较差外，其余各统计量均能较好的表征两序列相似程度，而且较K=6时各统计量的效果均稳中有升。这说明在K=7时，d2S、d2star表现依然优秀，说明在取K-tuple的长度为7时，利用两序列关联性特征量仍能较好的判断序列的相似程度；通过K-tuple在两序列间的距离来描述的Eu表现不俗，说明利用序列间距离也能很好地反应序列的相似程度。当K=8时，表征序列中K-tuple的Hao特征量和依然Ch表现很差，而其余三种各统计量均能较好的表征两序列相似程度。K=9时，如图3-4-f所示。Hao特征较K=8时有小幅回升，而其余各统计量均能较好的表征两序列相似程度。这说明在K=8时，通过期望值来预测序列的实际情况这一方法不稳定，容易受到K-tuple长度的干扰，因为不同长度的K-tuple在序列中出现的频率是不同的。d2S、d2star表现依然优秀，说明在取K-tuple的长度为9时，利用两序列关联性特征量仍为明智之举；通过K-tuple在两序列间的距离来描述的Eu虽有下降，但仍表现不俗，说明利用序列间距离也能很好地反应序列的相似程度。K-tuple的长度为10时，如图3-4-g所示。通过K-tuple在两序列间的距离来描述的Eu和Hao均出现了下滑，d2S、d2star表现依然优秀，这说明在取K-tuple的长度为10时，利用d2S、d2star两序列关联性特征量仍为明智之举；而对K-tuple较序列长度较长时，不宜使用Ch、Eu、Hao作为评价两序列是否相似的依据。说明当K-tuple相对序列较长时，刻画两序列间的距离较为困难，而且对于更长的K-tuple，通过期望来预测整体情况更难，也不宜用作反应序列的相似程度。综合来看，d2S、d2star始终保持稳定，其他三种算法随着K值增大而性能变弱。K为任意值时的ROC曲线下的面积没有出现偏离正常值，说明这两种方法的稳定性高，准确性强，从而体现了d2S和d2star方法的稳定性和相对其它方法的优越性。接下来我们重点分析d2S、d2star这两种算法对病毒和宿主细胞之间关联性的研究。3.5.3d2S和d2star算法受马尔科夫阶次的影响在上述前提条件下，结合图3-3和图3-4可知，利用两序列关联性特征量d2star和d2S均能较好的判断序列的相似程度(AUC都在0.93以上)，而且对全局比对和局部比对都相对稳定。在图3-5中，我们研究了d2star和d2S两种算法在不同的马尔科夫阶次下的AUC值，其中K=5，我们发现d2star和d2S统计值用0-2阶马尔科夫模型能都很好23 华南理工大学硕士学位论文地刻画两序列间的相似程度，而马尔科夫阶次为1时的AUC相对于马尔科夫阶次为0和2好一些。d2star和d2S算法在病毒识别中不仅精度高，而且在算法、时间复杂度和空间复杂度上都更占优势，即提高了序列非比对的精度，又节约了计算机资源，还节省了大量时间。因此，可以考虑在实际应用中推广此种办法对两序列进行评估。在接下来的分析中我们选择马尔科夫阶次为Morder=1，K=5参数下进行研究。图3-5K=5时d2S和d2star在不同Morder值下的ROC曲线3.6本章总结序列比较是生物信息中最基本、最重要的操作之一，通过序列比较可以发现生物序列中的功能、结构和进化的信息。生物序列分析中的序列非比对法是伴随着生物测序技术的进步而发展起来的以全基因组序列为主要研究对象的序列分析方法。与传统的比对方法相比，主要特点是计算的时间复杂度和空间复杂度较低，注重挖掘序列的整体特征而忽略序列的细节信息，特别适合于比较基因组学的研究。在本次实验中，我们使用了ROC曲线和AUC柱状图两种方法，对d2S，d2star，Eu，Ch，Hao算法性能进行了评价。从ROC曲线结果来看，在K值较低时，这五个算法性能表现均比较稳定，但是在K值较高时，Eu、Ch和Hao算法受到影响较大，而d2S和d2star算法几乎不受影响，表现稳定。从AUC值来看，五种算法受局部比对和全局比对影响不大，整体性能都很稳定；而对于马尔科夫阶数，d2S，d2star都几乎不受影响，但是在马尔科夫阶数为2时，d2S性能表现更好。因此我们认为d2S，d2star更适合于病毒和宿主细胞的研究。24 第四章用序列非比对法d2S和d2star结合邻接法NJ对病毒进行聚类研究第四章用序列非比对法d2S和d2star结合邻接法NJ对病毒进行聚类研究4.1系统树简介自达尔文时代起，许多生物学家都有一个梦想，那便是重建地球上所有生命的进化历史并以系统树的形式描述这部历史。经典系统发育学研究所涉及的特征主要是生物表型特征。通过经典系统发育学研究，进化学家已经得出了生物进化历史的主要框架。然而形态和生理性状的进化十分复杂，以至于不可能重建出完善的系统树，不同学者重建的系统树在细节上几乎总是有争议的。分子生物学的进展为系统发育学研究提供了新的方法。现在人们可以直接利用核酸序列或蛋白质氨基酸序列中的相关信息，作为物种的特征来进行系统发育分析。通过比较、分析序列之间的关系，构建系统树。进而阐明各个物种间的进化关系。系统发育进化是生物数据最自然也是最有意义的一种有序排列，并且系统树的不同分支还能够包含大量的进化信息。因此，不同领域的科学家都可以利用这些系统发育进化的信息来研究并阐明在不同生物水平上所发生的生物学过程。构建系统树的数据来源可以是表型数据和遗传数据，表型性关系定义为根据物体一组表型性状所获得的相似性，并由此可以画出表型分枝图。遗传性关系含有祖先的信息，因而可用于研究进化的途径，并由此可以画出进化分枝图。表型分枝图和进化分枝图两个术语已用于表示分别根据表型性的和遗传性的关系所建立的关系树。进化分枝图可以显示事件或类群间的进化时间，而表型分枝图则不需要时间概念。系统树，又可称为系统发生树，它是基于同源基因构建描述物种之间亲缘关系的系统树图。系统树一般为二叉树的形式，大多由一系列分支和节点组成，其中，每一个节点就代表了一个分类单元（通常把一个物种或序列作为一个分类单元），而通常节点之间的边线代表了物种间的亲缘关系，或者说进化关系，边线的长度长短则代表了种间的相似性的强弱。系统树可划分为有根树和无根树。有根树指的是单一个的节点即可指派为物种的共同的祖先，而从祖先节点出发只有独一无二的路径历经进化从而到达其他任何的节点。而对于无根树，无根树只表明了节点之间的关系，没有进化发生的方向的具体信息，大多都是通过引入外部群落或者外部参考物种，从而可以在无根树中指派其根节点。有根树与无根树如下图4-1和4-2所示：25 华南理工大学硕士学位论文图4-1有根树图4-2无根树4.2系统树的表示方法图4-3系统树简介图以上图4-3为例，一个简单的系统树是由根，节点，自展支持率以及进化枝组成的。对这些概念下面给出了解释。节点：表示一个分类单元，它可以是一个已存在的物种，也可以是一个祖先。进化枝：由两种或两种以上生物或DNA序列以及其祖先及所有后代组成的树枝。根：所有分类的共同祖先。进化分支长度：用数据表示的进化枝的变化程度。26 第四章用序列非比对法d2S和d2star结合邻接法NJ对病毒进行聚类研究4.3系统树的类型图4-4系统树的类型图如图4-4，系统树可以分为有根树和无根树，有根树有一个叫根的特殊节点，用来表示共同的祖先，由该点通过唯一路径产生其他节点，反映了树上物种或基因的时间顺序。无根树是指指明了种属的相互关系，没有确认共同祖先或进化途径。即反映分类单元之间的距离而不涉及谁是谁的祖先问题。要区分不同的进化路径，在系统树分析过程中必须加入一个或多个已知与分析序列关系较远的序列作为外类群。外类群可以辅助定位树根，外类群序列与其他序列间的差异必须比其他序列之间的差异更显著，外类群的选择对进化分析的结果影响较大。4.4本文案例病毒比原核生物的数量要多得多，其数量超过细菌10倍以上，估计是地球上最丰富的生物体。随着病毒数量越来越多，病毒的识别以及分类对于生物学的研究显得愈发重要。序列非比对统计法是基于字模式的比对，通过统计K-tuple在两条要比对的序列中出现的次数，并用统计打分值来判断两条序列的相似度。在这项研究中，我们从NCBI病毒基因组数据库下载了36个噬菌体的序列数据，并将36个噬菌体病毒分成4大类Podoviridae（10个噬菌体），Leviviridae（6个噬菌体），Siphoviridae（10个噬菌体），Myoviridae（10个噬菌体），如表4-1。27 华南理工大学硕士学位论文表4-136种病毒数据集的描述针对d2S和d2star这两种算法，我们选取相同马尔科夫阶次Morder=1和不同的K-tuple值对对4种类型的噬菌体进行了聚类，对这四类噬菌体，我们用不同的颜色标28 第四章用序列非比对法d2S和d2star结合邻接法NJ对病毒进行聚类研究注，相同颜色的噬菌体是同一个类别，对d2S我们发现K=4，6，8，10，可以很清晰地把4种噬菌体区分开，这四种颜色的噬菌体均按照我们最早分好类进行了聚类，而且受参数影响不是很大。分类效果也非常好。但是对于d2star算法，我们发现其也能基本把四种颜色的噬菌体分开，但是对标注为红色和黑色的两种噬菌体分类效果不是很好。而黄色和蓝色均能清晰的进行分类。整体来讲d2S和d2star对病毒进行识别聚类还是比较理想，特别是d2S算法可以准确的对病毒进行聚类进而识别未知的病毒。图4-5-ad2S在K=4时的系统树图4-5-bd2S在K=6时的系统树29 华南理工大学硕士学位论文图4-5-cd2S在K=8时的聚类树图4-5-dd2S在K=10时的聚类树30 第四章用序列非比对法d2S和d2star结合邻接法NJ对病毒进行聚类研究图4-6-ad2star在K=4时的聚类图4-6-bd2star在K=6时的聚类31 华南理工大学硕士学位论文图4-6-cd2star在K=8时的聚类图4-6-dd2star在K=10时的聚类4.5本章小结在对微生物核酸序列测定后，可通过对序列进行比对得出微生物物种间的关系。目前微生物聚落的构成通常比较复杂，包含着成百上千的位置基因序列。并且，随着宏基因组的发展，对微生物聚落的研究深入到对微生物聚落及其生存环境的研究，这一过程32 第四章用序列非比对法d2S和d2star结合邻接法NJ对病毒进行聚类研究增加了大量的未知的未经培养的微生物，因而增加了大量的未知基因序列。序列比对法非常依赖于用已知基因数据作为参考，因此，未知的基因序列给比对结果的准确性和完整性带来了巨大的影响和误差。所以，序列非比对法给宏基因组的深入研究提供了另一个选择。本章中我们使用两种非比对方法在不同K值下对四类已经标注好的噬菌体进行聚类，发现d2S和d2star对病毒进行识别聚类还是比较理想，受K值影响不大，特别是d2S算法可以准确的对病毒进行聚类进而识别未知的病毒。由此可以使用d2S算法对病毒进行聚类进而对病毒识别提供新途径。33 华南理工大学硕士学位论文第五章用序列非比对法d2S和d2star对病毒感染宿主细胞可能性的评估5.1病毒和宿主细胞基因相似性理论病毒由于可以显著的影响着原核生物的生命进程和生态系统功能,因此它们是限制其宿主细胞数量的一个重要因素。病毒仅靠自身并不能完成遗传和复制，为了繁殖，病毒需要注入一个活的有机体，即宿主细胞。它首先感染宿主细胞，然后劫持宿主细胞的复制机制，以产生子代病毒颗粒。细菌，古细菌和动物细胞都可以成为病毒的宿主细胞。尽管病毒感染宿主细胞的机制还没有完全得到解析，但有数据表明，一个病毒和它的宿主细胞的核酸序列之间含有相同的字模式（K-tuple），从而对于该宿主细胞来说这个病毒会比随机的其他病毒更具有相似性。由于病毒是依赖于它宿主细胞进行复制，我们假设病毒将采用与其宿主细胞类似的字模式，以最大限度地利用宿主细胞进行复制。5.2病毒和宿主细胞的序列非比对比较随着新一代测序技术的快速发展，特别是对大量基因组数据来说，病毒识别成为一个处理基因组数据非常重要和必不可少的步骤。通过深入分析大量生物学数据，根据测序数据，考虑病毒的宿主细胞和环境的关系，可以更好地了解病毒基因组的多样性和动态变化，以及病毒和它们的宿主细胞、环境之间的相互作用和病原体的致病性。通过使用最广泛的病毒鉴定方法，如序列搜索，系统发育，长度为N的序列的频率，贝叶斯分类器，和马尔科夫模型。随着新工具的不断改进，精度也在不断提高。但测序读段长度的减少和物种水平识别的准确性显著下降是所有当前算法的共同缺点。因此，为提高计算性能，使用短序列的物种或在子物种水平上进行病毒鉴定。在序列非比对法的基础上，我们根据病毒和宿主细胞的序列特点对其进行一定优化和调整。在此，需要用到基于K-tuple的频率特征统计量d2star和d2S统计量来刻画病毒和宿主细胞的关系。生物学中的K-tuple，是指长度为K的一小段基因序列。通过测序方法，利用K-tuple获取K-tuple在被测物种全序列中的散布情况，从而得到一个这段K-tuple基因序列的频率分布，这一小段基因序列在被测物种全序列中的分布组成表征该物种全序列的特征向量。因此，34 第五章用序列非比对法d2S和d2star对病毒感染宿主细胞可能性的评估两序列的比对可通过比较K-tuple的特征向量得到。所以，一个可行的利用序列特征统计量进行分析的流程如下：（1）分析长度为K的序列片段的特征向量；（2）利用特征向量计算两个序列片段的各项特征统计量；（3）利用特征统计量分析两序列的关系。考虑到病毒能感染宿主细胞的生化基础为，病毒能通过多种方式着床到宿主细胞上，并能与宿主细胞表面的受体氨基酸链进行信息交换和传递，从而改变宿主细胞的生化结构，使病毒能成功突破阻碍，进入到宿主细胞内。而这一过程和病毒与宿主细胞的基因表达紧密联系。为了从遗传分子层面探究病毒和宿主细胞的关联性，从基因库中选取一个宿主细胞的DNA基因序列，然后选取200个已知能感染该宿主细胞的病毒基因，同时我们选取了200个未知能否入侵宿主细胞的病毒。通过这200个模板病毒与宿主细胞基因的比对，利用序列非比对法得到相应的d2star、d2S特征统计量数据获得阈值。再利用阈值对病毒和宿主细胞关系进行探究。5.3最佳阈值的确定图5-1-aK=5时d2S的阈值图5-1-bK=5时d2star的阈值在以上分析基础上，选择Morder=1、K=5来确定d2star和d2S的最佳阈值。用d2star和d2S对200种已知能感染的病毒DNA序列与200种未知能否感染的病毒DNA序列分别与宿主细胞DNA序列进行非比对打分，然后将得分情况用ROC曲线描述，从而得到最佳阈值，结果如图5-1-a和5-1-b所示，假设能够找到一个阈值，它在分类时既不会错误地将负类识别为正类，又能正确识别出所有真正的正类，那么这个阈值一定是最佳35 华南理工大学硕士学位论文阈值，此时1-特异度为0，敏感度为1，该ROC曲线将经过点(0,1)。由于实际上许多曲线并不经过(0,1)，因此可认为，ROC曲线中最靠近点(0,1)的点是曲线的最佳阈值对应的点。这个点的意义是：花费了尽量少的成本(错误识别负类的概率)得到了尽可能多的收益(正确识别正类的概率)，所以可以认为它是最佳阈值点。利用d2S特征统计量，在K=5、Morder=1时，从ROC曲线上获得最佳点为（0.078,0.897），该点的阈值为0.34228；利用d2star特征统计量，在K=5、Morder=1时，从ROC曲线上获取到最佳点为（0.083,0.887），该点的阈值为0.22182。5.4最佳阈值应用实例表5-1d2star和d2S统计打分值和阈值的比较结果选取160组已经知道可以感染宿主细胞的病毒DNA序列和宿主细胞的DNA序列，获得160种d2star和d2S打分值，表5-1。将这160个打分值分别和d2star和d2S的最佳阈值进行比较，当打分值高于阈值时，认为病毒可以感染宿主细胞；当打分值低于阈值时，认为病毒不可以感染宿主细胞。表5-1中加粗的部分表示打分值低于最佳阈值，意味着病毒是不可以感染宿主细胞的，但事实上却是可以感染的，也就是说，160组中有d2S有8组判断失误，d2star有10处判断失误，错误率分别为5%和6%。d2S效果优于d2star。以上实验结果表明，利用d2star和d2S统计量判断病毒是否感染宿主细胞的方法切实有效，且判断准确率较高。36 第五章用序列非比对法d2S和d2star对病毒感染宿主细胞可能性的评估5.5本章小结人们早就认识到，未知的细菌和古细菌在许多生态系统中起重要作用，它们控制了重要的全球生物及地球化学循环，并对人类、动物以及农作物的健康产生各种影响，但关于病毒对宿主细胞的影响机制却难以确知。病毒能通过改变宿主细胞膜的生化性状侵入宿主细胞，然后通过控制宿主细胞基因表达，在宿主细胞内营造一个适合自身生长繁殖的有利环境。病毒还能通过调控宿主细胞内基因表达，使宿主细胞合成对自己有益的相关蛋白类物质，以促进自身在宿主细胞内的增值效率等。这些过程都离不开病毒和宿主细胞的基因调控，因此通过对病毒和宿主细胞的基因进行分析，可以归纳出探究病毒和宿主细胞关联性的有效方法。我们使用d2star和d2S统计量来对病毒和宿主细胞的DNA序列进行比对。对于感染宿主细胞的病毒来说，其DNA结构简单，序列相对较短，参与病毒翻译蛋白质的编码基因也相对较短，所以K-tuple的选取也应该与病毒的DNA结构相适应。文中利用d2star和d2S特征统计量对病毒的DNA序列和宿主细胞的DNA序列进行打分，将打分值与获得的阈值进行比较，从而判断该病毒是否能感染宿主细胞，获得了一种判别病毒和宿主细胞关联性的有效方法。研究结果表明，d2star和d2S统计量方法在判断病毒能否感染宿主细胞上表现优秀，值得期待。虽然相对简单的基于病毒和细菌宿主细胞的字模式向量的相似性的方法已经发展到研究病毒与宿主细胞的关联性，但这问题在精度方面明显不足。37 华南理工大学硕士学位论文第六章总结与展望自1995年Fleischmann等人完成了流感嗜血杆菌全基因组序列的测定以来，宏基因组的研究取得了长足的发展。海量的宏基因组数据的出现，也推动了基于传统生物学与计算机科学相结合的生物信息学的发展，从而促进了更多的对生物遗传进化信息进行探究的方法的诞生。而以进化学说为理论基础发展的序列比对法，在大量生物信息数据出现的情况下已不适用，因此，仅需使用少量内存资源和计算资源，且受序列长度、序列重组、变异等影响比较小的序列非比对法应用愈加广泛，使通过已知基因序列对未知基因序列进行探索成为了可能，也使人们可以深入研究物种之间的种群关系，以及微生物对于其他物种进化和环境的影响。宏基因组的研究经过了近十几年的飞速发展，目前已经呈现了研究技术从“多样”到“趋同”、研究目标由“组成”转向“功能”、研究内容由“静态”[25]到“动态”、研究角度从“局部”到“整体”、研究方法从“单一”到“综合”的发展趋势。因此，面对目前越来越多的生物学数据，传统的生物学已无法有效处理如此海量的数据，更多的交叉学科的科学家需要投身其中，为宏基因组学以及生物信息学贡献出自己的一份力量。通过序列非比对法测定未知基因，进而从中获得特定的功能基因，不仅可以用于新的工业用酶等生物活性物质的筛选，而且在新药的研发以及在解决环境污染的生物修复等方面都具有广阔的应用前景。通过对这些海量数据的挖掘、分析、研究，我们人类可以更好地了解自己以及生物圈，对认识生命起源产生巨大的影响，同时，通过非序列比对法对未知生物信息探究，将会给疫苗研制等领域带来源源不断的动力。在本文中，我们已经对五种序列非比对法进行了比较，也选出了目前比较优秀的比对方法——d2star和d2S，基于此，我们下一步的研究方向是如何进一步改进算法，从而加快算法的比对速率，提高算法的比对准确性。38 参考文献参考文献1.陈铭著.生物信息学（第二版）.科学出版,2013.2.郝柏林,张淑誉著.生物信息学（第二版）.上海科学技术出版社,2002.3.龙海侠等著.进化算法在生物多序列比对中的应用.清华大学出版社,2017.4.王俊等译著.生物序列分析.科学出版社,2010.5.翟中和等著.细胞生物学（第三版）.高等教育出版社,2007.6.丁海珈,范淑琴著.分子细胞生物学.科学出版社,2001.7.AReyes,LVBlanton,SCao,etal.GutDNAviromesofMalawiantwinsdiscordantforsevereacutemalnutrition.ProceedingsoftheNationalAcademyofSciences,112:11941–11946,2015.8.DPaez-Espino,EAEloe-Fadrosh,GAPavlopoulos,etal.Uncoveringearth’svirome.Nature,536,2016.9.GLima-Mendez,JVanHelden,AToussaint,etal.Reticulaterepresentationofevolutionaryandfunctionalrelationshipsbetweenphagegenomes.MolecularBiologyandEvolution,25:762–777,2008.10.MGZhang,LPYang,RJie,etal.Predictionofvirus-hostinfectiousassociationbysupervisedlearningmethods.BMCBioinformatics,18(suppl3):60,2017.11.CGaliez,MSiebert,FEnault,etal.Wish:whoisthehost?predictingprokaryotichostsfrommetagenomicphagecontigs.Bioinformatics,33:3113–3114,2017.12.BEDutilh,NCassman,KMcNair,etal.Ahighlyabundantbacteriophagediscoveredintheunknownsequencesofhumanfaecalmetagenomes.NatureCommunications5,2014.13.JMNorman,SAHandley,MTBaldridge,etal.Disease-specificalterationsintheentericviromeininflammatoryboweldisease.Cell,160:447–460,2015.14.JRBrum,JCIgnacio-Espinoza,SRoux,etal.Patternsandecologicaldriversofoceanviralcommunities.Science,348:1261498,2015.15.AReyes,MHaynes,NHanson,etal.Virusesinthefaecalmicrobiotaofmonozygotictwinsandtheirmothers.Nature,466:334–338,2010.16.DAPearce,KKNewsham,MAThorne,etal.Metagenomicanalysisofasouthernmaritimeantarcticsoil.Front.Microbiol,3:403.10.3389/fmicb.2012.00403,2012.39 华南理工大学硕士学位论文17.SRoux,FEnault,BLHurwitz,etal.Virsorter:miningviralsignalfrommicrobialgenomicdata.PeerJ,3:e985,2015.18.RAEdwards,KMcNair,KFaust,etal.Computationalapproachestopredictbacteriophage–hostrelationships.FEMSMicrobiologyReviews,40:258–272,2016.19.SRoux,SJHallam,TWoyke,etal.Viraldarkmatterandvirus–hostinteractionsresolvedfrompubliclyavailablemicrobialgenomes.Elife,4:e08490,2015.20.NAAhlgren,JRen,YYLu,etal.Alignment-freed∗2oligonucleotidefrequencydissimilaritymeasureimprovespredictionofhostsfrommetagenomically-derivedviralsequences.NucleicAcidsResearch,45:39–53,2017.21.TFSmith,MSWaterman.Identificationofcommonmolecularsubsequences.JournalofMolecularBiology,147(1):195–197,1981.22.SFAltschul,WGish,WMiller,etal.Basiclocalalignmentsearchtool.JournalofMolecularBiology,215(3):403–410,1990.23.WJKent.BLAT:theBLAST-likealignmenttool.GenomeResearch,12(4):656–664,2002.24.HWang,ZXu,LGao,etal.Afungalphylogenybasedon82completegenomesusingthecompositionvectormethod.BMCEvolutionaryBiology,9:195,2009.25.SJun,GSims,GWu,etal.Whole-proteomephylogenyofprokaryotesbyfeaturefrequencyprofiles:Analignment-freemethodwithoptimalfeatureresolution.ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,107(1):133–138,2010.26.XML,LWan,JLi,etal.Newpowerfulstatisticsofalignment-freesequencecomparisonunderapatterntransfermodel.JournalofTheoreticalBiology,284(1):106–116,2011.27.JRen,KSong,FSun,etal.Multiplealignment-freesequencecomparison.Bioinformatics,29(21):2690–2698,2013.28.YYLu,KTang,JRen,etal.Cafe:acceleratedalignment-freesequenceanalysis.NucleicAcidsResearch,45(W1),2017.29.IUlitsky,DBurstein,TTuller,etal.Theaveragecommonsubstringapproachtophylogenomicreconstruction.JournalofComputationalBiology,13(2):336–350,2006.30.LYang,XZhang,HFu,etal.Anestimatorforlocalanalysisofgenomebasedontheminimalabsentword.JournalofTheoreticalBiology,395:23–30,2016.31.YWang,KHill,SSingh,etal.Thespectrumofgenomicsignatures:fromdinucleotidestochaosgamerepresentation.Gene,346(1):173–185,2005.40 参考文献32.SSTYau,CYu,RHe.Aproteinmapanditsapplication.DNAandCellBiology,27(5):241–250,2008.33.CYin,SSTYau.Animprovedmodelforwholegenomephylogeneticanalysisbyfouriertransform.JournalofTheoreticalBiology,382:99–110,2015.34.SVinga.Informationtheoryapplicationsforbiologicalsequenceanalysis.BriefingsinBioinformatics,15(3):376–389,2014.35.JSAlmeida.Sequenceanalysisbyiteratedmaps,areview.BriefingsinBioinformatics,15(3):369–375,2014.36.AZielezinski,SVinga,JAlmeida,etal.Alignment-freesequencecomparison:benefits,applications,andtools.GenomeBiology,18(1):186,2017.37.Bonham-Carter,JSteele,DBastola.Alignment-freegeneticsequencecomparisons:areviewofrecentapproachesbywordanalysis.BriefingsinBioinformatics,15(6):890–905,2014.38.SVinga,JAlmeida.Alignment-freesequencecomparisonareview.Bioinformatics,19(4):513–523,2003.39.GSims,SJun,GWu,etal.Alignment-freegenomecomparisonwithfeaturefrequencyprofiles(FFP)andoptimalresolutions.ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,106(8):2677–2682,2009.40.LNarlikar,NMehta,SGalande,etal.Onesizedoesnotfitall:Onhowmarkovmodelorderdictatesperformanceofgenomicsequenceanalyses.NucleicAcidsResearch,41(3):1416–1424,2013.41.HTeeling,JWaldmann,TLombardot,etal.Tetra:aweb-serviceandastandaloneprogramfortheanalysisandcomparisonoftetranucleotideusagepatternsindnasequences.BMCBioinformatics,5(1):163,2004.42.DTPride,TMWassenaar,CGhose,etal.Evidenceofhost-virusco-evolutionintetranucleotideusagepatternsofbacteriophagesandeukaryoticviruses.BMCGenomics,7(1):8,2006.43.DWillner,RVThurber,FRohwer.Metagenomicsignaturesof86microbialandviralmetagenomes.EnvironmentalMicrobiology,11(7):1752–1766,2009.44.MARagan,GBernard,CXChan.Molecularphylogeneticsbeforesequences:oligonucleotidecatalogsask-merspectra.RNABiology,11(3):176–185,2014.45.CXChan,GBernard,OPoirion,etal.Inferringphylogeniesofevolvingsequenceswithoutmultiplesequencealignment.ScientificReports,4(39),2013.46.KSong,JRen,ZZhai,etal.Alignment-freesequencecomparisonbasedon41 华南理工大学硕士学位论文next-generationsequencingreads.JournalofComputationalBiology,20:64–79,2013.47.JQi,BWang,BLHao.Wholeproteomeprokaryotephylogenywithoutsequencealignment:ak-stringcompositionapproach.JournalofMolecularEvolution,58:1–11,2004.48.HAlmagor.AMarkovanalysisofDNAsequences.JournalofTheoreticalBiology,104:633–645,1983.49.PAPevzner,MYBorodovsky,AAMironov.Linguisticsofnucleotidesequencesi:thesignificanceofdeviationsfrommeanstatisticalcharacteristicsandpredictionofthefrequenciesofoccurrenceofwords.JournalofBiomolecularStructureandDynamics,6:1013–1026,1989.50.JHong.Predictionofoligonucleotidefrequenciesbasedupondinucleotidefrequenciesobtainedfromthenearestneighboranalysis.NucleicAcidsResearch,18:1625–1628,1990.51.JArnold,AJCuticchia,DANewsome,etal.Mono-throughhexanucleotidecompositionofthesensestrandofyeastDNA:aMarkovchainanalysis.NucleicAcidsResearch,16:7145–7158,1988.52.PJAvery.Theanalysisofintrondataandtheiruseinthedetectionofshortsignals.JournalofMolecularEvolution,26:335–340,1987.53.GReinert,DChew,FSun.Alignment-freesequencecomparison(I):statisticsandpower.JournalofComputationalBiology:AJournalofComputationalMolecularCellBiology,16(12):1615-1634,2009.42 附录1附录143 华南理工大学硕士学位论文攻读硕士学位期间取得的研究成果已发表（包括已接受待发表）的论文，以及已投稿、或已成文打算投稿、或拟成文投稿的论文情况（只填写与学位论文内容相关的部分）：相当于发表或学位论投稿刊发表的被索引序文的哪作者（全体作者，按顺序排列）题目物名卷期、年收录情号一部分称、级月、页码况（章、别节）华南理工大学用序列非比对法评估2017刘雪梅，臧翔，黄天来，杨哲，学报1病毒感染宿主细胞的45（11）第五章EI收录李文，叶宇中，胡珊(自然可能性科学版)Xue-meiLiu,XiangZang,StudyontheRelationTian-LaiHuang,ZheYang,Wenbetweenvirusandhost2016,CPCI收2CIS第三章Li,Yu-ZhongYe,ShanHu,andcellbyalignment-free391-394录JingLisequencecomparison注：在“发表的卷期、年月、页码”栏：1如果论文已发表，请填写发表的卷期、年月、页码；2如果论文已被接受，填写将要发表的卷期、年月；3以上都不是，请据实填写“已投稿”，“拟投稿”。不够请另加页。44 致谢致谢行文至此，我的论文写作也接近了尾声，心中感慨万千，有喜悦之情，有解脱之感，但更多的是感激之心。我要在这里向所有在这篇论文完成过程给予我鼓励、支持、帮助的人表达由衷的感谢。首先要感谢我的导师——刘雪梅老师。本文是在刘雪梅老师的耐心教导和悉心指导下完成的。从论文的选题到写作，从论文的结构到文章的润色，从数据的挑选到计算程序的验证，再到数据逻辑的推理，刘老师都认真地审阅并给我提出了宝贵的建议和意见，不断给我支持、鼓励和帮助。刘老师的严谨治学、渊博学识、耐心教学、宽容胸怀一直不断地在鞭策我。可以说，没有她的精心指导，我就无法最终完成本论文。刘老师以其严肃的研究态度，严谨的治学精神，精益求精的工作作风，深深地激励和感染了我，她谨慎的做事态度也将是我终身学习的榜样。其次，要感谢师兄师弟，黄天来、叶宇中、李文、黄管大同学在论文的撰写过程中，无私的帮助和鼓励。最后，要特别感谢我的家人。在求学路上，是他们在我身后的默默付出与无私帮助，才使我可以全身心投入到学习以及论文的撰写中。他们对我的爱以及支持，促使我在学业上不断追求进步，克服一切困难。我一直感恩，感恩于我可以拥有一个如此温馨的家庭，让我所有的一切都可以在你们这里得到理解与支持，我爱我的家！本课题的顺利结题，离不开所有人的支持与帮助。再次衷心感谢所有给予过关心帮助的老师、家人、同学和朋友。45 1
