《基于hadoop的序列比对和进化树构建方法.ppt》由会员分享，可在线阅读，更多相关《基于hadoop的序列比对和进化树构建方法.ppt（16页珍藏版）》请在三一办公上搜索。
1、基于hadoop的序列比对和进化树构建方法,(1)整体框架介绍(2)序列比对设计方案(3)进化树构建设计方案(4)目前进展及进一步工作,1、整体框架介绍,输入：fasta格式的DNA序列文件输出：DNA序列比对文件、DNA序列进化树文件流程：(1)对输入文件进行格式处理(2)多序列比对(3)对比对结果做聚类预处理(4)进化树构建,1、整体框架介绍,TS00019ACCGyTGCTGACAACGACGCCAGTGCASGACGTS00020ACCGTGCGACACACGACGACGTTTGCGATGTS00021ATC,TS00019ACCGTGCTGACAACGACGCCAGTGCAGACGT
2、S00020ACCGTGCGACACACGACGACGTTTGCGATG,Key value TS00019:ACCGTGCTGACAACGAC GCCAGTTS00020:ACCGTGCGACACACGACGACGTTT,序列比对：输入：TS00019:ACCGTGCTGACAACGAC GCCAGTTS00020:ACCGTGCGACACACGACGACGTTT输出：TS00019ACCGTGCTGACA-ACGACGCCAGT-TS00020ACCGTGC-GACACACGACGAC-GTTT,进化树构建输入：TS00019ACCGTGCTGACA-ACGACGCCAGT-TS00020
3、ACCGTGC-GACACACGACGAC-GTTT输出：(TS00019,TS00020),TS00058),(TS00033,TS18),2、序列比对设计方案,汇总中心序列：new_s1 ACCGT-GCTGACA-ACGACGCCAGT-new_s1 ACCGT-GCTGACA-ACG-ACGCCAGTnew_s3 ACCGTGCTGACA-ACG-ACGCCAG-T-new_s4 ACCGT-GCTGACAACG-ACGCCAGT-final_s ACCGT-GCTGACA-ACG-ACGCCAG-T-,2、序列比对设计方案,Map1函数的输入输出格式,2、序列比对设计方案,Map2函
4、数的输入输出格式,3、进化树构建设计方案,比对后的序列计算其距离矩阵,输入数据：TS0001ACCGTGCTGACA-ACGACGCCAGT-TS0002ACCGTGC-GACACACGACGAC-GTTTTS0003ACCGTGC-GACCCACGTCGAC-GCTTTS0004ACCGTGC-GATGACGGTCGACG-CTTTS0005ACCGTG-GACGCCGTGACGACG-CTT,3、进化树构建设计方案,(1)Neighbour-joining 进化树构建方法 n 次循环迭代，时间复杂度 O(n3)(2)进化树本质上是一个聚类过程(3)预处理的聚类算法要求 时间复杂度低、粒度大
5、、子集合规模合理,3、进化树构建设计方案,进化树算法数据输入格式setID seq_name seq1 TS0019 ACGTGCTG-ACGTG-ACGTA1 TS0020 ACGTGCGTA-AGTCG-ATGAC2 TS0021 ACGTGGC-ACGTGCGATGAC2 TS0022 ACGT-CAGCTACGTGC-ACGT3 TS0023 ACGTG-GTGACGTGACGT-AG,3、进化树构建设计方案,MapReduce 的输入输出格式,3、进化树构建设计方案,reduce 函数的输入输出 输入-NJ 算法-输出 key value key value Name1 Seq1 s
6、eq_r1(s1,s2),s4)Name2 Seq2 Name3 Seq3 seq_r2(s7,s8),(s9,s10)Name_n Seq_n,3、进化树构建设计方案,聚类算法探索 聚类要求(1)时间复杂度低，避免聚类影响整体效率(2)聚类粒度大，精度低，防止破坏进化树结构(3)子集合簇相对均衡，控制算法效率,3、进化树构建设计方案,目前采用的聚类方法.一趟聚类算法：输入：比对后的DNA序列集合输出：聚类后的子集合过程：步骤1：初始化时，聚类集合为空，从数据集中读取一个新的对象；步骤2：以这个对象构造一个新的簇；步骤3：若已到数据集末尾，则转步骤6)，否则读入新的对象，计算它与 每个已有簇之
7、间的距离，并选择与它距离最小的簇；步骤4：若最小距离超过给定的阈值r，转步骤2)；步骤5：否则将该对象并入该簇并更新该簇，转步骤3）；步骤6：输出聚类后的子集合；,4、目前进展及进一步工作,程序有1600行代码，21个类，56个函数 所有核心代码都已经做了详细的注释,4、目前进展及进一步工作,对聚类算法的设想(1)一趟聚类+Apriori 算法(2)图遍历算法(3)最小割集算法(4)谱聚类算法,4、目前进展及进一步工作,一趟聚类+Apriori 算法执行k次一趟聚类算法 1,2,4,3,5,8,6,7 1,2,3,4,5,6,7,8 1,2,4,3,5,6,7,8 1,2,4,3,5,6,7,8,
