《基于hadoop的序列比对和进化树构建方法》由会员分享，可在线阅读，更多相关《基于hadoop的序列比对和进化树构建方法（16页珍藏版）》请在金锄头文库上搜索。
1、基于基于hadoop的序列比对和进化树构建方法的序列比对和进化树构建方法(1) 整体框架介绍(2) 序列比对设计方案(3) 进化树构建设计方案(4) 目前进展及进一步工作1、整体框架介绍输入：fasta格式的DNA序列文件输出：DNA序列比对文件、DNA序列进化树文件流程：(1) 对输入文件进行格式处理 (2) 多序列比对 (3) 对比对结果做聚类预处理 (4) 进化树构建1、整体框架介绍 TS00019ACCGyTGCTGACAACGACGCCAGTGCASGACGTS00020ACCGTGCGACACACGACGACGTTTGCGATGTS00021ATC TS00019ACCGTGCTG
2、ACAACGACGCCAGTGCAGACGTS00020ACCGTGCGACACACGACGACGTTTGCGATG Key value TS00019:ACCGTGCTGACAACGAC GCCAGTTS00020:ACCGTGCGACACACGACGACGTTT序列比对：输入： TS00019:ACCGTGCTGACAACGAC GCCAGTTS00020:ACCGTGCGACACACGACGACGTTT输出：TS00019ACCGTGCTGACA-ACGACGCCAGT-TS00020ACCGTGC-GACACACGACGAC-GTTT进化树构建输入：TS00019ACCGTGCTGAC
3、A-ACGACGCCAGT-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函数的
4、输入输出格式2、序列比对设计方案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
6、 value Name1 Seq1 seq_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：若已到数据集
7、末尾，则转步骤6)，否则读入新的对象，计算它与 每个已有簇之间的距离，并选择与它距离最小的簇；步骤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
