劉桂霞，李廣力，李 涵

(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130012)

云平臺(tái)下基因-基因相互作用識(shí)別算法

劉桂霞，李廣力，李 涵

(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130012)

針對(duì)現(xiàn)有的快速方差分析算法進(jìn)行并行可擴(kuò)展性改進(jìn)，設(shè)計(jì)一種高效的并行計(jì)算模型，并提出一種基于MapReduce模型的基因-基因相互作用識(shí)別算法——MR-ANOVA算法.該算法有效解決了現(xiàn)有基因-基因相互作用識(shí)別算法在海量數(shù)據(jù)規(guī)模下普遍存在計(jì)算復(fù)雜度過(guò)高的問(wèn)題.實(shí)驗(yàn)結(jié)果表明，該算法充分利用了云平臺(tái)的并行計(jì)算能力，隨著數(shù)據(jù)量的增大，加速比逐漸接近于集群數(shù)量，可高效準(zhǔn)確地完成基因-基因相互作用的識(shí)別.

基因-基因相互作用;MapReduce模型;云計(jì)算

1 基于方差分析的基因-基因相互作用識(shí)別算法

1.1 方差分析方法

方差分析方法［5］旨在將整體數(shù)據(jù)間的差異分為若干組內(nèi)數(shù)據(jù)差異與組間數(shù)據(jù)差異，從而進(jìn)行比較，判定某個(gè)小組是否為有效數(shù)據(jù).由于多基因作用的影響，表現(xiàn)型在某種意義上非常復(fù)雜，而利用方差分析可有效分析連續(xù)的表現(xiàn)型，從而找出影響遺傳變異的可能因素.因此方差分析被認(rèn)為是一種度量單核苷酸多態(tài)與表現(xiàn)型間關(guān)聯(lián)性的標(biāo)準(zhǔn)統(tǒng)計(jì)學(xué)方法，并常用于表現(xiàn)型關(guān)聯(lián)性的定量研究中.但由于雙位點(diǎn)相關(guān)性檢測(cè)非常耗時(shí)，方差分析并不能很好地適用于全基因組范圍內(nèi)，因此要引入更高效的處理方法.快速方差分析算法，即FastANOVA算法［3］，是一種結(jié)合大量置換檢驗(yàn)，并運(yùn)用批處理方式對(duì)單核苷酸多態(tài)對(duì)進(jìn)行方差分析的優(yōu)化算法.由于該算法利用相互獨(dú)立的多組表現(xiàn)型值排列而得出方差分析的上界，篩選出了少數(shù)有意義的候選單核苷酸多態(tài)對(duì)，所以僅需在少數(shù)候選SNP對(duì)中進(jìn)行方差分析即可，且不會(huì)丟失有意義的SNP對(duì).此外，某些統(tǒng)計(jì)量對(duì)于每一組別是特定的，從而在不同的置換檢驗(yàn)中僅需計(jì)算一次.

1.2 算法并行可拓展性的改進(jìn)

FastANOVA算法在計(jì)算閾值Fα?xí)r使用了迭代方法，在計(jì)算中使用一個(gè)全局更新表不斷對(duì)Fα進(jìn)行更新，這種迭代更新的方法使算法的并行可擴(kuò)展性較差.考慮到算法對(duì)Fα進(jìn)行更新的操作只是一種優(yōu)化操作，并不會(huì)對(duì)程序最終運(yùn)行結(jié)果產(chǎn)生影響，所以在對(duì)算法的改進(jìn)中本文使用局部的更新表替代全局更新表，使算法具有更好的并行可擴(kuò)展性，并易于在云平臺(tái)下實(shí)現(xiàn)并行化.

2 基于MapReduce模型的并行化算法

MapReduce模型處理數(shù)據(jù)的過(guò)程可抽象成兩個(gè)函數(shù):Map和Reduce.Map將問(wèn)題分解成多個(gè)任務(wù)，Reduce將分解后多個(gè)任務(wù)的處理結(jié)果進(jìn)行綜合［6］.程序開(kāi)發(fā)者只需設(shè)計(jì)出該模型中的Map和Reduce函數(shù)，而并行編程中可能出現(xiàn)的各類復(fù)雜問(wèn)題，如工作調(diào)度、容錯(cuò)處理和網(wǎng)絡(luò)通信等，都會(huì)由MapReduce框架負(fù)責(zé)解決［7-8］.

基于MapReduce的快速方差分析算法(即MR-ANOVA)分為兩個(gè)階段，每階段將作為Hadoop云計(jì)算框架中的一個(gè)任務(wù)完成.假設(shè)Xi和Xj均代表基因型值，而Y代表表現(xiàn)型排列，{X1，X2，…，Xn}是n個(gè)被關(guān)注SNP的集合.第一階段進(jìn)行置換檢驗(yàn)，Map函數(shù)將SNP分組，并盡可能平均的將分組發(fā)送至Reduce.Reduce函數(shù)接收分組，計(jì)算對(duì)于分組中給定的Xi在所有XiXj(i＜j)中p種不同排列的F值.第一階段結(jié)束后，通過(guò)對(duì)結(jié)果的排序查找操作可得出用于求解第二階段的Fα值.第二階段進(jìn)行基因-基因相互作用的求解，Map函數(shù)將SNP分組，并盡可能平均的將分組發(fā)送至Reduce.Reduce函數(shù)接收分組，對(duì)于分組中給定的Xi，計(jì)算所有XiXj(i＜j)的F值，并輸出F＞Fα的SNP對(duì).

2.1 高效的并行計(jì)算模型

在云平臺(tái)上進(jìn)行并行計(jì)算時(shí)，理想情況是集群中每個(gè)節(jié)點(diǎn)處理同樣多的數(shù)據(jù)，這樣能使每個(gè)節(jié)點(diǎn)的運(yùn)算時(shí)間基本相同，此時(shí)算法可得到最高效的并行計(jì)算效果.對(duì)于兩位點(diǎn)的基因-基因相互作用識(shí)別，需要計(jì)算全部SNP對(duì)的F值［9］.通常情況下，N個(gè)SNP兩位點(diǎn)的基因-基因相互作用識(shí)別中，對(duì)于編號(hào)為i的SNP，需要計(jì)算XiXj(i＜j≤n)的全部F值，共需要計(jì)算n-i個(gè)F值，隨著i的不斷增大，計(jì)算量逐漸減少，所以將每個(gè)Xi平均分配給集群中的節(jié)點(diǎn)進(jìn)行計(jì)算無(wú)法取得良好的并行效果.針對(duì)該問(wèn)題，本文提出一種兩位點(diǎn)基因-基因相互作用識(shí)別的高效并行計(jì)算模型.

假設(shè)有m個(gè)節(jié)點(diǎn)用于計(jì)算，在該模型中，SNPi與SNPn-i+1將組成一個(gè)分組，每個(gè)分組的計(jì)算量為n，分組個(gè)數(shù)為n/2，每個(gè)節(jié)點(diǎn)將計(jì)算(n/2)/m個(gè)分組，此時(shí)每個(gè)節(jié)點(diǎn)的計(jì)算量會(huì)相對(duì)均衡，將有效提高算法在云平臺(tái)下并行計(jì)算的效率，該并行模型如圖1所示.本文將這種高效的并行計(jì)算模型應(yīng)用到快速方差分析算法中，不僅解決了云平臺(tái)中各節(jié)點(diǎn)負(fù)載均衡的問(wèn)題，同時(shí)也顯著提高了并行計(jì)算的效率.

圖1 并行計(jì)算模型Fig.1 Parallel computing model

2.2 MR-ANOVA算法

2.2.1 Map函數(shù)和Reduce函數(shù) MR-ANOVA的第一階段通過(guò)置換檢驗(yàn)獲取方差分析的閾值Fα，第二階段根據(jù)閾值Fα求出所有F＞Fα的SNP對(duì).第一階段Map函數(shù)的輸入〈key，value〉鍵值對(duì)中，key為行號(hào)，value為Reduce的數(shù)量NR，Map函數(shù)將SNP按并行化模型進(jìn)行分組，并盡可能均勻的將分組分配至各個(gè)Reduce中，將Reduce編號(hào)與SNP編號(hào)以〈key'，value'〉鍵值對(duì)形式發(fā)送.第二階段的Map函數(shù)與第一階段的結(jié)構(gòu)和功能相同.Map函數(shù)描述如下:

在MR-ANOVA第一階段Reduce函數(shù)的輸入〈key，value〉鍵值對(duì)中，key為Reduce編號(hào)，value為需要計(jì)算的SNP編號(hào)集合，Reduce函數(shù)的功能是對(duì)value中的每個(gè)編號(hào)i計(jì)算所有XiXj(i＜j)全部排列(1～p)的F值，并發(fā)送〈key'，value'〉鍵值對(duì)，其中key'為排列編號(hào)，value'為F值.第二階段的Reduce函數(shù)中去掉了置換檢驗(yàn)的步驟，其他步驟與第一階段相同.Reduce函數(shù)描述如下:

2.2.2 算法的MapReduce框架 在MR-ANOVA算法中包含兩個(gè)階段，在Hadoop平臺(tái)下，本文建立了job1和job2兩個(gè)任務(wù)分別對(duì)應(yīng)算法的兩個(gè)階段.在job1任務(wù)完成后，根據(jù)給定的Ⅰ型錯(cuò)誤值和置換檢驗(yàn)次數(shù)對(duì)job1任務(wù)的計(jì)算結(jié)果排序及查找操作，可獲取第一階段置換檢驗(yàn)得出的Fα值.job2任務(wù)使用Fα值進(jìn)行算法的第二階段，找出符合條件的SNP對(duì)，并輸出相關(guān)結(jié)果的信息.MR-ANOVA算法的整體框架如圖2所示.

圖2 MR-ANOVA算法框架Fig.2MR-ANOVA framework

3 實(shí)驗(yàn)結(jié)果及分析

本文使用Hadoop開(kāi)源平臺(tái)下的MapReduce框架，在本地集群上進(jìn)行部署.本地集群由6臺(tái)主機(jī)組成，其中1臺(tái)主機(jī)作為master，5臺(tái)主機(jī)作為slave，集群中每個(gè)節(jié)點(diǎn)的CPU頻率均為2.80 GHz，內(nèi)存容量為1 Gb.平臺(tái)使用Hadoop1.0.4版本，操作系統(tǒng)為Ubuntu 10.04，使用JAVA語(yǔ)言實(shí)現(xiàn).

在云平臺(tái)下并行化算法的目的主要是為了解決基因-基因相互作用識(shí)別中密集計(jì)算的問(wèn)題，本文以加速比(speedup)作為指標(biāo)對(duì)算法性能進(jìn)行檢測(cè).加速比是指同一算法在一臺(tái)主機(jī)上的運(yùn)行所需時(shí)間與并行化后在具有m個(gè)節(jié)點(diǎn)的集群上運(yùn)行所需時(shí)間的比值，該指標(biāo)常用于測(cè)試并行化算法運(yùn)行效率提高的程度.加速比用Sp表示，表達(dá)式為Sp=Tv/Tm，其中Tm表示在具有m個(gè)節(jié)點(diǎn)的集群上完成MRANOVA算法所花費(fèi)的時(shí)間;Tv表示在單個(gè)主機(jī)上運(yùn)行算法所花費(fèi)的時(shí)間.

本文實(shí)驗(yàn)使用的測(cè)試數(shù)據(jù)為來(lái)自Broad/MIT(http://www.broadinstitute.org/)的小鼠基因數(shù)據(jù)，利用NPUTE填補(bǔ)缺失的數(shù)據(jù)［10］，并通過(guò) Jackson Lab(http://jaxmice.jax.org/)查詢了小鼠對(duì)應(yīng)的Cardiovascular(blood pressure)表現(xiàn)型.為了更好體現(xiàn)MR-ANOVA算法的優(yōu)勢(shì)，實(shí)驗(yàn)使用不同規(guī)模的集群運(yùn)行算法.實(shí)驗(yàn)中，不同的Ⅰ型錯(cuò)誤值α也將導(dǎo)致出現(xiàn)不同的結(jié)果.實(shí)驗(yàn)使用的程序參數(shù)如下:Ⅰ型錯(cuò)誤值α=0.1，個(gè)體數(shù)為35個(gè)，置換檢驗(yàn)次數(shù)為100次.測(cè)試的SNP數(shù)量分別為1 000，2 000，5 000和10 000.

圖3 測(cè)試結(jié)果Fig.3 Experimental results

MR-ANOVA算法利用 Hadoop完成 Map與Reduce的任務(wù)，最終完成基因-基因相互作用的識(shí)別過(guò)程，算法加速比測(cè)試結(jié)果如圖3所示.由圖3可見(jiàn)，隨著SNP數(shù)量的不斷增大，Hadoop平臺(tái)可有效減小算法的時(shí)間消耗，加速比有顯著提高. Hadoop平臺(tái)節(jié)點(diǎn)間的數(shù)據(jù)傳輸及任務(wù)分配有一定的開(kāi)銷，當(dāng)SNP數(shù)量較小時(shí)，集群運(yùn)算所產(chǎn)生的加速效果并不明顯.加速比隨著集群規(guī)模增大而不斷增大，可見(jiàn)隨著節(jié)點(diǎn)數(shù)量的增大，算法時(shí)間消耗將進(jìn)一步減少.

實(shí)驗(yàn)結(jié)果表明，本文提出的MR-ANOVA算法更適用于大規(guī)模數(shù)據(jù)計(jì)算，即當(dāng)需要分析的SNP數(shù)量越大時(shí)，并行化加速效果越明顯.其主要原因在于數(shù)據(jù)量較大時(shí)，Hadoop平臺(tái)下數(shù)據(jù)操作的開(kāi)銷所占總時(shí)間的比例較小.MR-ANOVA算法利用云平臺(tái)減輕了基因-基因相互作用識(shí)別算法密集計(jì)算的負(fù)擔(dān)，是一種高效的基因-基因相互作用識(shí)別算法.

綜上所述，本文提出的MR-ANOVA算法是對(duì)FastANOVA算法的一種并行化改進(jìn)，有效減少了基因-基因相互作用識(shí)別算法中密集計(jì)算的時(shí)間消耗.MR-ANOVA算法充分利用了云平臺(tái)的并行計(jì)算能力，可更高效完成基因-基因相互作用的識(shí)別.

［1］ ZHANG Xiang，ZOU Fei，WANG Wei.FastChi:An Efficient Algorithm for Analyzing Gene-Gene Interactions［J］. Pacific Symposium on Biocomputing，2009，14:528-539.

［2］ ZHANG Xiang，HUANG Shunping，ZOU Fei，et al.Tools for Efficient Epistasis Detection in Genome-Wide Association Study［J］.Source Code for Biology and Medicine，2011，6(1):1.

［3］ ZHANG Xiang，ZOU Fei，WANG Wei.Fastanova:An Efficient Algorithm for Genome-Wide Association Study［C］// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM，2008:821-829.

［4］ 李建江，崔健，王聃，等.MapReduce并行編程模型研究綜述［J］.電子學(xué)報(bào)，2011，39(11):2635-2642. (LI Jianjiang，CUI Jian，WANG Dan，et al.Survey of MapReduce Parallel Programming Model［J］.Acta Electronica Sinica，2011，39(11):2635-2642.)

［5］ Bolton S.Analysis of Variance［J］.Pharmaceutical Statistics:Practical and Clinical Applications，1997，737: 265-325.

［6］ 李成華，張新訪，金海，等.MapReduce:新型的分布式并行計(jì)算編程模型［J］.計(jì)算機(jī)工程與科學(xué)，2011，33(3):129-135.(LI Chenghua，ZHANG Xinfang，JIN Hai，et al.MapReduce:A New Programming Model for Distributed Parallel Computing［J］.Computer Engineering＆Science，2011，33(3):129-135.)

［7］ 劉鵬.云計(jì)算［M］.2版.北京:電子工業(yè)出版社，2011:21-24.(LIU Peng.Cloud Computing［M］.2nd ed. Beijing:Publishing House of Electronics Industry，2011:21-24.)

［8］ 劉鵬.實(shí)戰(zhàn)Hadoop:開(kāi)啟通向云計(jì)算的捷徑［M］.北京:電子工業(yè)出版社，2011:60-62.(LIU Peng.Action in Hadoop:Open the Shortcut to Cloud Computing［M］.Beijing:Publishing House of Electronics Industry，2011: 60-62.)

［9］ Wang Z，Wang Y，Tan K L，et al.eCEO:An Efficient Cloud Epistasis Computing Model in Genome-Wide Association Study［J］.Bioinformatics，2011，27(8):1045-1051.

［10］ Roberts A，McMillan L，Wang W，et al.Inferring Missing Genotypes in Large SNP Panels Using Fast Nearest-Neighbor Searches over Sliding Windows［J］.Bioinformatics，2007，23(13):i401-i407.

(責(zé)任編輯:韓 嘯)

Algorithms for Detecting Gene-Gene Interactions Based on Cloud Platform

LIU Guixia，LI Guangli，LI Han
(College of Computer Science and Technology，Jilin University，Changchun 130012，China)

The authors proposed an optimized algorithm for detecting gene-gene interactions based on MapReduce model，namely，MR-ANOVA.Compared with the traditional FastANOVA algorithm，this algorithm puts forward the concept of parallel processing during which an efficient parallel computing model is used.This improvement can make the problem of high computational complexities with the large-scale data of the existing algorithms solved.Analyzing results of the experiment，we can draw the following conclusion: MR-ANOVA algorithm can make the best use of the promising power of parallelism computation of the cloud platform.As the scale of the data becomes larger，the speedup is more close to the number of clusters.Thus，this optimized algorithm can detect epistatic interaction more efficiently.

gene-gene interaction;MapReduce model;cloud computing

TP311.1

A

1671-5489(2014)03-0546-05

10.13413/j.cnki.jdxblxb.2014.03.26

全基因組關(guān)聯(lián)研究(genome-wide association studies，GWAS)是在全基因組范圍內(nèi)對(duì)單核苷酸多態(tài)(single nucleotide polymorphism，SNP)與表現(xiàn)型間潛在關(guān)系的研究，它能有效檢測(cè)哪些遺傳因素可導(dǎo)致個(gè)體間性狀形成的差異，對(duì)于人類疾病等生物研究領(lǐng)域有重要意義.傳統(tǒng)的全基因組關(guān)聯(lián)研究?jī)H關(guān)注于單個(gè)單核苷酸多態(tài)與表現(xiàn)型間的關(guān)系，而未考慮SNP間相互作用并共同改變表現(xiàn)型的情況，這種不同基因位點(diǎn)同時(shí)控制相同性狀的現(xiàn)象被稱為基因-基因相互作用.目前，已有很多應(yīng)用于基因-基因相互作用的識(shí)別算法，如FastChi算法［1］、利用凸優(yōu)化的COE算法［2］和基于方差分析的FastANOVA算法［3］等.目前的大部分算法雖減小了搜索空間，但仍不能真正解決大量的單核苷酸多態(tài)對(duì)相互作用產(chǎn)生的密集計(jì)算問(wèn)題.MapReduce是一種云平臺(tái)下的并行編程模型，能連接大量主機(jī)的計(jì)算資源，從而形成規(guī)模巨大的集群，適用于處理海量數(shù)據(jù)的并行計(jì)算［4］.本文使用Hadoop平臺(tái)，利用MapReduce模型對(duì)FastANOVA算法進(jìn)行并行化改進(jìn).

2014-03-10.

劉桂霞(1963—)，女，漢族，博士，教授，博士生導(dǎo)師，從事計(jì)算智能理論、云計(jì)算技術(shù)及其應(yīng)用的研究，E-mail:liugx @jlu.edu.cn.通信作者:李廣力(1992—)，男，漢族，從事計(jì)算智能理論、云計(jì)算技術(shù)及其應(yīng)用的研究，E-mail:calculatinggod@ foxmail.com.

國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào):61373051;61175023)、吉林省科技發(fā)展計(jì)劃重點(diǎn)項(xiàng)目(批準(zhǔn)號(hào):20140204004GX)和吉林大學(xué)“大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃”項(xiàng)目(批準(zhǔn)號(hào):2013B53205).