發(fā)布時(shí)間：2018-01-14 17:42

  本文關(guān)鍵詞：多序列星比對算法的改進(jìn)及其在Spark中的并行化研究　出處：《計(jì)算機(jī)科學(xué)》2017年10期 　論文類型：期刊論文

  更多相關(guān)文章： 多序列比對 星比對算法 K-mer Spark RDD

【摘要】：多序列星比對算法在確定中心序列時(shí)需要計(jì)算任意兩個(gè)輸入序列的距離及分?jǐn)?shù),其較高的時(shí)間復(fù)雜度耗費(fèi)了大量時(shí)間,因此提出了通過綜合計(jì)算每個(gè)序列產(chǎn)生的k-mers及各個(gè)k-mer在各序列中出現(xiàn)的次數(shù)來確定k-mers的拼接選擇,由k-mers進(jìn)行拼接從而得到中心序列。進(jìn)而,在雙序列比對過程中采用搜索兩個(gè)序列最大相似子串的思想,改進(jìn)的星比對算法的精度在一定程度上得到了明顯提升。接著,將改進(jìn)的星比對算法在Spark中進(jìn)行并行化設(shè)計(jì)與實(shí)現(xiàn)。采用Spark的Yarn-Client運(yùn)行模式,對正常人線粒體的多組數(shù)據(jù)進(jìn)行實(shí)驗(yàn),分析了算法性能上的不足及改進(jìn)方向。
[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.
【作者單位】： 內(nèi)蒙古農(nóng)業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院;
【基金】：國家自然科學(xué)基金(61063004,61363006) 內(nèi)蒙古自然科學(xué)基金(2015MS0605,2015MS0626,2015MS0627) 內(nèi)蒙古教育廳高校研究項(xiàng)目(NJZC059) 教育部留學(xué)人員基金([2014]1685) 內(nèi)蒙古自治區(qū)科技計(jì)劃項(xiàng)目:穿透降水量GSM網(wǎng)絡(luò)在線監(jiān)測與數(shù)據(jù)傳輸系統(tǒng)的研制資助
【分類號】：Q811.4;TP338.6
【正文快照】： 到稿日期:2017-07-05返修日期:2017-08-15本文受國家自然科學(xué)基金(61063004,61363006),內(nèi)蒙古自然科學(xué)基金(2015MS0605,基因序列比對是生物信息學(xué)的重要研究議題之一。通過比對計(jì)算序列間的相似性,可以探索和發(fā)現(xiàn)新的基因結(jié)構(gòu)和功能,同時(shí)也可以獲得不同物種間的進(jìn)化聯(lián)系。進(jìn)一

【相似文獻(xiàn)】

相關(guān)期刊論文 前1條

1 楊瑤;桑延超;多麗君;;蛋白質(zhì)三級結(jié)構(gòu)預(yù)測的并行化算法[J];科技創(chuàng)新導(dǎo)報(bào);2008年18期

相關(guān)碩士學(xué)位論文 前3條

1 楊睿;基于并行計(jì)算的基因序列快速比對方法研究[D];浙江大學(xué);2015年

2 王秋文;基于Hadoop的全基因組關(guān)聯(lián)研究系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D];天津大學(xué);2012年

3 張晶;ABEEMσπ/MM模型中能量求解的并行化[D];遼寧師范大學(xué);2010年

，

本文編號：1424644