数据处理、光谱分析 与数据挖掘 - 邹权.PPT

* Tianjin University Tianjin University Tianjin University Tianjin University Tianjin University Tianjin University Tianjin University Tianjin University Tianjin University Tianjin University Tianjin University Tianjin University DNA多序列比对中的算法技术和并行方法 邹权 (PH.D.Professor) 天津大学 计算机科学与技术学院 2015.12 Different from Mapping, Assembly, BLAST Multiple Sequence Alignment(MSA): What Where Multiple Sequence Alignment(MSA): What Where Different from Mapping, Assembly, BLAST BLAST: Basic Local Alignment Search Tool Query Database Output Multiple Sequence Alignment(MSA): What Where input Output Multiple Sequence Alignment(MSA): What Where Multiple Sequence Alignment Multiple DNA Sequence Alignment Multiple Similar DNA Sequence Alignment Phylogenetic tree Virus sequences Population SNV calling Techniques for similar DNA MSA 1. k-band Dynamic Programming j i 0 1 c 2 a 3 t 4 g 5 t 0 0 -1 1 a -1 -1 1 2 c -2 1 0 0 3 g 0 0 -1 2 4 c -1 -1 1 1 5 t 1 0 3 6 g 3 2 -1 -1 -4 -5 0 K-band 2. Center star strategy Techniques for similar DNA MSA S1 S2 S3 S4 S5 S1 S2 S3 S4 S5 tree alignment Center star strategy Center Star for Multiple Sequence Alignment input sequences search sum up update final result … How to set k for k-band? S=AGACGTAGCCTAGCAGCCCGTACT T=AGACCTAGCTAGCAGCCCGTACACT S1=AGACGT S2=AGCCTA S3=GCAGCC S4=CGTACT Detecting the matching region with Trie Center Star for Multiple Sequence Alignment input sequences search sum up update final result … trie trees From Trie to Suffix Tree Trie S1=AGACGT S2=AGCCTA S3=GCAGCC S4=CGTACT Suffix Tree S1=AGACGTAGCCTAGCAGCCCGTACT S2= GACGTAGCCTAGCAGCCCGTACT S3= ACGTAGCCTAGCAGCCCGTACT S4= CGTAGCCTAGCAGCCCGTACT S5= GTAGCCTAGCAGCCCGTACT S6= TAGCCTAGCAGCCCGTACT S7= AGCCTAGCAGCCCGTACT … Greedy search with suffix tree T=GTCCTGAAGCTCCGT 1234567890123456 S=GTCCGAAGCTCCGG (1,1,4)