多序列星比对算法的改进及其在Spark中的并行化研究

发布时间：2018-01-14 17:42

本文关键词：多序列星比对算法的改进及其在Spark中的并行化研究　出处：《计算机科学》2017年10期 　论文类型：期刊论文

【摘要】：多序列星比对算法在确定中心序列时需要计算任意两个输入序列的距离及分数,其较高的时间复杂度耗费了大量时间,因此提出了通过综合计算每个序列产生的k-mers及各个k-mer在各序列中出现的次数来确定k-mers的拼接选择,由k-mers进行拼接从而得到中心序列。进而,在双序列比对过程中采用搜索两个序列最大相似子串的思想,改进的星比对算法的精度在一定程度上得到了明显提升。接着,将改进的星比对算法在Spark中进行并行化设计与实现。采用Spark的Yarn-Client运行模式,对正常人线粒体的多组数据进行实验,分析了算法性能上的不足及改进方向。
[Abstract]:The multi-sequence star alignment algorithm needs to calculate the distance and fraction of any two input sequences when determining the central sequence, and its high time complexity consumes a lot of time. Therefore, by synthetically calculating the number of k-mers produced by each sequence and the times of each k-mer appearing in each sequence, we propose to determine the splicing selection of k-mers. The center sequence is obtained by splicing by k-mers. Furthermore, the idea of searching for the maximum similarity substring of two sequences is adopted in the process of double sequence alignment. The precision of the improved star alignment algorithm is improved to some extent. The improved star alignment algorithm is designed and implemented in Spark. Using the Yarn-Client operation mode of Spark, the experiment is carried out on the multiple groups of data of normal human mitochondria. The performance of the algorithm and the improvement direction are analyzed.
【作者单位】：内蒙古农业大学计算机与信息工程学院;
【基金】：国家自然科学基金(61063004,61363006) 内蒙古自然科学基金(2015MS0605,2015MS0626,2015MS0627) 内蒙古教育厅高校研究项目(NJZC059) 教育部留学人员基金([2014]1685) 内蒙古自治区科技计划项目:穿透降水量GSM网络在线监测与数据传输系统的研制资助
【分类号】：Q811.4;TP338.6
【正文快照】： 到稿日期:2017-07-05返修日期:2017-08-15本文受国家自然科学基金(61063004,61363006),内蒙古自然科学基金(2015MS0605,基因序列比对是生物信息学的重要研究议题之一。通过比对计算序列间的相似性,可以探索和发现新的基因结构和功能,同时也可以获得不同物种间的进化联系。进一

【相似文献】