云平臺下基因-基因相互作用識別算法

劉桂霞，李廣力，李 涵

(吉林大學計算機科學與技術學院，長春130012)

云平臺下基因-基因相互作用識別算法

劉桂霞，李廣力，李 涵

(吉林大學計算機科學與技術學院，長春130012)

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

基因-基因相互作用;MapReduce模型;云計算

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

1.1 方差分析方法

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

1.2 算法并行可拓展性的改進

FastANOVA算法在計算閾值Fα時使用了迭代方法，在計算中使用一個全局更新表不斷對Fα進行更新，這種迭代更新的方法使算法的并行可擴展性較差.考慮到算法對Fα進行更新的操作只是一種優(yōu)化操作，并不會對程序最終運行結果產生影響，所以在對算法的改進中本文使用局部的更新表替代全局更新表，使算法具有更好的并行可擴展性，并易于在云平臺下實現(xiàn)并行化.

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

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

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

2.1 高效的并行計算模型

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

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

圖1 并行計算模型Fig.1 Parallel computing model

2.2 MR-ANOVA算法

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

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

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

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

3 實驗結果及分析

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

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

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

圖3 測試結果Fig.3 Experimental results

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

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

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

［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］.電子學報，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］.計算機工程與科學，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］ 劉鵬.云計算［M］.2版.北京:電子工業(yè)出版社，2011:21-24.(LIU Peng.Cloud Computing［M］.2nd ed. Beijing:Publishing House of Electronics Industry，2011:21-24.)

［8］ 劉鵬.實戰(zhàn)Hadoop:開啟通向云計算的捷徑［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.

(責任編輯:韓 嘯)

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

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

2014-03-10.

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

國家自然科學基金(批準號:61373051;61175023)、吉林省科技發(fā)展計劃重點項目(批準號:20140204004GX)和吉林大學“大學生創(chuàng)新創(chuàng)業(yè)訓練計劃”項目(批準號:2013B53205).