《基于hadoop的序列比对和进化树构建方法》由会员分享，可在线阅读，更多相关《基于hadoop的序列比对和进化树构建方法（16页珍藏版）》请在装配图网上搜索。
1、基于基于hadoop的序列比对和进化树构建方法的序列比对和进化树构建方法(1)整体框架介绍(2)序列比对设计方案(3)进化树构建设计方案(4)目前进展及进一步工作1、整体框架介绍输入：fasta格式的DNA序列文件输出：DNA序列比对文件、DNA序列进化树文件流程：(1)对输入文件进行格式处理 (2)多序列比对 (3)对比对结果做聚类预处理 (4)进化树构建1、整体框架介绍 TS00019ACCGyTGCTGACAACGACGCCAGTGCASGACGTS00020ACCGTGCGACACACGACGACGTTTGCGATGTS00021ATC TS00019ACCGTGCTGACAACGAC
2、GCCAGTGCAGACGTS00020ACCGTGCGACACACGACGACGTTTGCGATG Key value TS00019:ACCGTGCTGACAACGAC GCCAGTTS00020:ACCGTGCGACACACGACGACGTTT序列比对：输入：TS00019:ACCGTGCTGACAACGAC GCCAGTTS00020:ACCGTGCGACACACGACGACGTTT输出：TS00019ACCGTGCTGACA-ACGACGCCAGT-TS00020ACCGTGC-GACACACGACGAC-GTTT进化树构建输入：TS00019ACCGTGCTGACA-ACGACGC
3、CAGT-TS00020ACCGTGC-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、序列比对设计方
4、案Map2函数的输入输出格式3、进化树构建设计方案比对后的序列计算其距离矩阵输入数据：TS0001ACCGTGCTGACA-ACGACGCCAGT-TS0002ACCGTGC-GACACACGACGAC-GTTTTS0003ACCGTGC-GACCCACGTCGAC-GCTTTS0004ACCGTGC-GATGACGGTCGACG-CTTTS0005ACCGTG-GACGCCGTGACGACG-CTT3、进化树构建设计方案(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-AG3、进化树构建设计方案MapReduce 的输入输出格式3、进化树构建设计方案reduce 函数的输入输出 输入 -NJ 算法 -输出 key value key value Name1 Seq1 seq
6、_r1 (s1,s2),s4)Name2 Seq2 Name3 Seq3 seq_r2 (s7,s8),(s9,s10)Name_n Seq_n3、进化树构建设计方案聚类算法探索 聚类要求 (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
基于hadoop的序列比对和进化树构建方法
