多序列比对 讲课课件

多序列比对中的算法技术和并行方法DifferentfromMapping,Assembly,BLASTMultipleSequenceAlignment(MSA):What&WhereMultipleSequenceAlignment(MSA):What&WhereDifferentfromMapping,Assembly,BLASTBLAST:BasicLocalAlignmentSearchToolQueryDatabaseOutputMultipleSequenceAlignment(MSA):What&WhereinputOutputMultipleSequenceAlignment(MSA):What&WhereMultipleSequenceAlignmentMultipleDNASequenceAlignmentMultipleSimilar

DNASequenceAlignmentOurFocusPhylogenetictreeVirussequencesPopulationSNVcalling…ApplicationTechniquesforsimilarDNAMSA1.k-bandDynamicProgramming

ji01c2a3t4g5t00-11a-1-112c-21003g00-124c-1-1115t1036g32-1-1-4-50K-band2.CenterstarstrategyTechniquesforsimilarDNAMSAS1S2S3S4S5S1S2S3S4S5treealignmentCenterstarstrategyCenterStarforMultipleSequenceAlignmentstep1

inputsequences

search

step2

sumup

updatefinalresult…Howtosetkfork-band?S=AGACGTAGCCTAGCAGCCCGTACTT=AGACCTAGCTAGCAGCCCGTACACTS1=AGACGTS2=AGCCTAS3=GCAGCCS4=CGTACTDetectingthematchingregionwithTrieCenterStarforMultipleSequenceAlignmentstep1

inputsequences

search

step2

sumup

updatefinalresult…trietreesFromTrietoSuffixTreeTrieS1=AGACGTS2=AGCCTAS3=GCAGCCS4=CGTACTSuffixTreeS1=AGACGTAGCCTAGCAGCCCGTACTS2=GACGTAGCCTAGCAGCCCGTACTS3=ACGTAGCCTAGCAGCCCGTACTS4=CGTAGCCTAGCAGCCCGTACTS5=GTAGCCTAGCAGCCCGTACTS6=TAGCCTAGCAGCCCGTACTS7=AGCCTAGCAGCCCGTACT…GreedysearchwithsuffixtreeT=GTCCTGAAGCTCCGT1234567890123456S=GTCCGAAGCTCCGG(1,1,4)(5,6,9)step1

inputsequences

search

step2

sumup

updatefinalresult…ExtremeMSAforVerySimilarDNASequencesExperiments100humanmitochondriagenomesequences16klength(1555KB)CenterStarSuffixtreecenterstarTriecenterstarK-bandcenterstarExtreme

TrieExtremesuffixtreeRunningtime12933.2s24.8s15.6s10.9s19.7s5.4sOuroutput1558KBClustalΩ1627KBMapReduceforCenterStarFrameSoftware/soft/halign/

QuanZou,QinghuaHu,MaozuGuo,GuohuaWang.HAlign:FastMultipleSimilarDNA/RNASequenceAlignmentBasedontheCentreStarStrategy.Bioinformatics.2015,31(15):2475-2481HalignServerLink:45:8080/Halign/DatasetNumberMinimumlengthMaximumlengthAveragelengthFilesize672165561657916569.710MB67200---1.1GB672000---11GB10845380715991442.8156MB101162180716291388.51.4GB17892194895459.015MB1789200---1.5GB17892000---15GBDNA/RNA/Protein各大数据集基本信息

timeavgSPtimeavgSPtimeavgSPtimeavgSPtimeavgSPMUSCLE6h15m81--------MAFFT1m20s152---->24h26743--HAlign2m12s19126m35s1915h28m1911h32s156603h15m32079HAlign-II14s19510m24s1951h25m19523m34s1662059m42s35956DNA/RNA各大数据集与经典方法的实验对比HAlign采用其速度最快的Hadoop+后缀树方案；HAlign-II采用其速度最快的Spark+后缀树方案。集群环境：由12台工作站组成，每台工作站配备Ubuntu16.04操作系统，IntelXeonE5-2620处理器，384GB内存，Hadoop2.7版本以及Spark2.0版本。Protein各大数据集与经典方法的实验对比HAlign采用其速度最快的Hadoop+Smith-Waterman方案；HAlign-II采用其速度最快的Spark+Smith-Waterman方案。集群环境：由12台工作站组成，每台工作站配备Ubuntu16.04操作系统，IntelXeonE5-2620处理器，384GB内存，Hadoop2.7版本以及Spark2.0版本。

timeavgSPtimeavgSPtimeavgSPMUSCLE------MAFFT5m34s925----SparkSW1m56s100950m51s10094h34m1009HAlign-II30s113110m12s11311h5m1131DNA/RNA/Protein各大数据集在超算上不同节点的实验对比MSA策略：基本动态规划法。超算环境：山东济南超算中心，MPI方案。优势：加速效果明显，适合密集计算任务。劣势