李華兵，楊　昆

(杭州電子科技大學(xué)計(jì)算學(xué)院，浙江 杭州 310018)

?

利用滑動(dòng)窗口和KNN算法識(shí)別差異甲基化區(qū)域

李華兵，楊昆

(杭州電子科技大學(xué)計(jì)算學(xué)院，浙江 杭州 310018)

摘要：針對(duì)現(xiàn)有差異甲基化區(qū)域DMRs識(shí)別方法中過(guò)度刪除顯著性弱的甲基化位點(diǎn)、DMRs長(zhǎng)度受限以及不能直接處理多類的問(wèn)題，提出了一種利用滑動(dòng)窗口和KNN算法識(shí)別不同類別間DMRs的算法.算法先通過(guò)滑動(dòng)窗口結(jié)合KNN分類器篩選候選區(qū)域，再根據(jù)誤差率合并候選區(qū)域得到DMRs.真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)表明，算法的分類性能、聚類指數(shù)明顯優(yōu)于對(duì)照算法，擴(kuò)展了對(duì)照的Ong算法識(shí)別的DMRs長(zhǎng)度，并能發(fā)現(xiàn)Ong算法未發(fā)現(xiàn)的DMRs.

關(guān)鍵詞：差異甲基化區(qū)域；滑動(dòng)窗口；KNN分類器；多類問(wèn)題；聚類指數(shù)

0引言

DNA甲基化是指在DNA甲基轉(zhuǎn)移酶(DNA methyltransferase，DNMTS)作用下，將甲基添加到堿基上，是一種重要的表觀遺傳修飾[1].不同條件下的生物學(xué)樣本之間存在差異甲基化區(qū)域(Differentially methylated regions，DMRs)，可能參與到基因表達(dá)的調(diào)控，進(jìn)而影響基因功能.相關(guān)研究表明，相對(duì)于單個(gè)位點(diǎn)獨(dú)立的識(shí)別方法，針對(duì)整個(gè)區(qū)域的識(shí)別方法更有生物學(xué)上的價(jià)值.DMRs識(shí)別與通常意義上的特征選擇有顯著區(qū)別：通常的特征選擇往往假定特征間無(wú)關(guān)聯(lián)性，然而DMRs是基因組上有位置關(guān)聯(lián)的一個(gè)區(qū)域，而且長(zhǎng)的DMRs更有生物價(jià)值.識(shí)別DMRs是當(dāng)前研究領(lǐng)域中重要且新穎的研究問(wèn)題，有別于通常的特征選擇問(wèn)題.目前，已有多個(gè)識(shí)別DMRs方法的提出，主要分3類：一類是通過(guò)分析計(jì)算一個(gè)區(qū)域中每個(gè)位點(diǎn)的差異來(lái)確定一個(gè)DMR，如bump hunting算法[2]和Slieker算法[3]，這類算法缺點(diǎn)是過(guò)度刪除了一些顯著性弱的單個(gè)位點(diǎn)；第二類算法是通過(guò)相鄰位點(diǎn)間的相關(guān)性，先聚類甲基化位點(diǎn)，然后估計(jì)每組聚類間差異性，如Ong算法[4]，這類算法的不足之處是在識(shí)別DMRs之前區(qū)域長(zhǎng)度受限；第三類算法是一種利用判別分析的DDA算法[5]，這類算法針對(duì)兩個(gè)類別的問(wèn)題，不能直接應(yīng)用于多類別問(wèn)題.針對(duì)上述存在的問(wèn)題，本文提出了一種利用滑動(dòng)窗口和K-近鄰(k-Nearest Neighbor，KNN)分類器的DMRs識(shí)別算法(Slide Windows KNN Algorithm,SWKA)，并通過(guò)實(shí)驗(yàn)分析對(duì)比了算法的有效性和準(zhǔn)確度.

1問(wèn)題的描述和SWKA算法

1.1問(wèn)題的描述

令p個(gè)位點(diǎn)n個(gè)樣本的DNA甲基化數(shù)據(jù)看作一個(gè)矩陣M=(xij)n×p，其中p個(gè)位點(diǎn)看作p個(gè)特征，代表p個(gè)維度，每個(gè)行向量ti=(xi1,xi2,…,xip)可看作為模式識(shí)別中的一個(gè)模式(pattern)，其中xij是芯片測(cè)出的樣本ti位點(diǎn)j的甲基化水平值.不同類別樣本中其DNA上存在甲基化程度明顯差異的CpG位點(diǎn)，具有位置關(guān)聯(lián)的差異甲基化位點(diǎn)構(gòu)成DMRs.給定多個(gè)類別的DNA甲基化數(shù)據(jù)，識(shí)別基因組上連續(xù)的DMRs是本文的研究問(wèn)題，本文主要針對(duì)Infinium 450 K甲基化數(shù)據(jù)開展工作.

1.2SWKA算法

SWKA算法是利用滑動(dòng)窗口結(jié)合KNN分類器識(shí)別DMRs算法.算法詳細(xì)流程如圖1所示，首先劃分各個(gè)染色體，探針不均勻的分布在染色體上，如圖1(a)所示，其中圓圈表示位點(diǎn)，并設(shè)定窗口滑動(dòng)步長(zhǎng)k；利用滑窗方式將所要分析片段劃分為位置關(guān)聯(lián)的小片段(種子)，如圖1(b)，其中實(shí)心和空心圓圈分別表示甲基化位點(diǎn)和非甲基化位點(diǎn)；再利用KNN分類器估計(jì)每個(gè)種子對(duì)樣本的分類能力，選取分類誤差率小于誤差率閾值的種子為DMRs種子，如圖1(c)；在滿足合并后分類誤差率小于合并前的原則下，將有重疊的DMRs種子合并，得到候選DMRs，如圖1(d)；在相鄰候選DMRs間距離小于一定長(zhǎng)度和合并后的分類效果優(yōu)于合并前的條件下對(duì)2個(gè)相鄰候選DMRs進(jìn)行合并，并對(duì)其進(jìn)行顯著性檢驗(yàn)，最后得到滿足P值條件的DMRs，如圖1(e).獲取本文算法源代碼，發(fā)送主題為“獲取利用滑動(dòng)窗口和KNN分類器識(shí)別差異甲基化區(qū)域算法代碼”的電子郵件到通信作者或者第一作者郵箱lucky_leehb@163.com.本文算法偽代碼如下所述：

圖1　識(shí)別DMRs的詳細(xì)流程

2實(shí)驗(yàn)結(jié)果與分析

2.1實(shí)驗(yàn)環(huán)境和數(shù)據(jù)來(lái)源

本文實(shí)驗(yàn)在windows10 64-bit，Intel CPU i5 2.5 G四核、內(nèi)存8.0 GB的PC上完成.

真實(shí)實(shí)驗(yàn)數(shù)據(jù)集(從GEO數(shù)據(jù)庫(kù)(http://www.ncbi.nlm.nih.gov/geo/)下載)是Infinium 450 K的4個(gè)年齡組甲基化數(shù)據(jù)集，來(lái)自GSE36064[6]，GSE33233[7]和GSE30870[7]，包含78個(gè)小孩樣本、19個(gè)中年樣本、新生兒和百歲以上老人樣本各19個(gè)，每個(gè)樣本包含485 577個(gè)位點(diǎn).采用KNNimpute法[8]對(duì)每組缺失數(shù)據(jù)估計(jì).實(shí)驗(yàn)中采用留一法交叉驗(yàn)證(LOOCV)，其分類誤差率閾值e為0.05，KNN分類器參數(shù)K為5，P閾值a為0.05，滑動(dòng)窗口滑動(dòng)步長(zhǎng)k為2，相鄰位點(diǎn)間距不大于1 000 bp.DDA和Ong算法是最新的識(shí)別DMRs方法，因?yàn)镈DA法不能直接處理多類問(wèn)題，所以本文采用Ong等人提出的DMRs識(shí)別算法作為實(shí)驗(yàn)對(duì)照方法.

2.2結(jié)果分析

本文采用參考聚類驗(yàn)證技術(shù)的Silhouette index[9]聚類指數(shù)和分類誤差率為評(píng)價(jià)指標(biāo)來(lái)考查所識(shí)別的DMRs.聚類指數(shù)是采用一個(gè)全局Silhouette index值GSu來(lái)作為聚類劃分的有效評(píng)價(jià)指標(biāo)，GS值越大表示聚類劃分效果越好，計(jì)算公式如下，詳細(xì)信息查閱文獻(xiàn)[9].

(1)

在對(duì)4個(gè)年齡組甲基化數(shù)據(jù)中，本文SWKA算法共識(shí)別出220個(gè)DMRs，使用Ong算法共識(shí)別出3 841個(gè)DMRs.本文識(shí)別出的220個(gè)DMRs中有161個(gè)區(qū)域不同于使用Ong算法計(jì)算出來(lái)的DMRs，兩者重疊區(qū)域有59個(gè).在重疊區(qū)域中有8個(gè)(13.56%)擴(kuò)展了Ong算法識(shí)別的DMRs長(zhǎng)度，11個(gè)(18.64%)與Ong識(shí)別的DMRs相同，22個(gè)(37.29%)與Ong識(shí)別的DMRs有重合，還有18個(gè)(30.51%)是包含于Ong發(fā)現(xiàn)的DMRs中，如圖2所示.

圖2　重疊DMRs劃分圖

為了進(jìn)一步考查所識(shí)別的DMRs的有效性，本文進(jìn)行如下驗(yàn)證：1)以單個(gè)DMR為特征計(jì)算原始數(shù)據(jù)上單個(gè)DMR聚類指數(shù)，指數(shù)越大聚類效果越好.SWKA方法識(shí)別的DMRs中有208個(gè)都明顯大于Ong算法所識(shí)別的DMRs聚類指數(shù)，如圖3(a)；2)利用單個(gè)DMR為特征對(duì)原始數(shù)據(jù)采用KNN分類，計(jì)算LOOCV誤差率，誤差率越小分類性能越優(yōu).SWKA方法發(fā)現(xiàn)的DMRs中有208個(gè)都明顯小于Ong算法識(shí)別的DMRS誤差率，如圖3(b)；3)計(jì)算SWKA能識(shí)別而Ong法未能識(shí)別的DMRs聚類指數(shù)和分類誤差率并與之比較，在兩種指標(biāo)上新識(shí)別的DMRs都優(yōu)于Ong算法識(shí)別的DMRs，如圖4所示.

不同類別在DMR的維度空間中具有良好的可分性，本文方法識(shí)別出的前6個(gè)DMRs在不同類別上的平均甲基化水平如圖5所示，從圖5中可看出，DMR在不同類別上平均甲基化水平存在明顯的差異.通過(guò)與對(duì)照方法的實(shí)驗(yàn)結(jié)果比較，SWKA方法擴(kuò)展了對(duì)照方法識(shí)別出的DMRs長(zhǎng)度，比如Ong方法在1號(hào)染色體上識(shí)別出的一個(gè)DMR為[40 090,40 091]，而SWKA算法識(shí)別的DMR為[40 088，40 089，40 090，40 091]，其在4個(gè)類別上的平均甲基化水平如圖5中的DMR04所示，并且還發(fā)現(xiàn)了對(duì)照方法未發(fā)現(xiàn)的DMRs，比如圖5中DMR01，DMR02，DMR03.

綜上所述，本文提出的SWKA算法識(shí)別的差異甲基化區(qū)域在聚類指數(shù)和誤差率的比較上整體都優(yōu)于Ong等人提出的DMRs識(shí)別算法，也就是說(shuō)，SWKA算法識(shí)別的DMRs比對(duì)照算法識(shí)別的DMRs差異性更顯著.SWKA方法還擴(kuò)展了對(duì)照方法識(shí)別出的DMRs長(zhǎng)度以及發(fā)現(xiàn)對(duì)照方法未發(fā)現(xiàn)的DMRs，經(jīng)過(guò)真實(shí)實(shí)驗(yàn)數(shù)據(jù)上的驗(yàn)證，本文方法準(zhǔn)確有效.

圖3　SWKA與Ong識(shí)別的DMRs的聚類驗(yàn)證和交叉驗(yàn)證結(jié)果

圖4　SWKA全新識(shí)別的DMRs與Ong識(shí)別的DMRs的聚類驗(yàn)證和交叉驗(yàn)證結(jié)果

圖5　DMRs在不同類別上的平均甲基化水平

3結(jié)束語(yǔ)

本文在分析最新的DMRs識(shí)別算法的基礎(chǔ)上，提出了一種利用滑動(dòng)窗口和KNN分類器識(shí)別不同年齡組間存在的DMRs算法.算法能直接運(yùn)用于多類別的情況，不僅擴(kuò)展了DMRs長(zhǎng)度，還識(shí)別出對(duì)照的Ong算法未發(fā)現(xiàn)的DMRs.本文算法也可以應(yīng)用于癌癥樣本的DMRs識(shí)別或者其他領(lǐng)域的特征選擇問(wèn)題.

參考文獻(xiàn)

[1]楊昆,張彥斌,戴勝冬,等.DNA甲基化的重要特征[J].生物物理學(xué)報(bào),2012,28(11):910-922.

[2]JAFFFAE,MURAKAMIP,LEEH,etal.Bumphuntingtoidentifydifferentiallymethylatedregionsinepigeneticepidemiologystudies[J].Internationaljournalofepidemiology, 2012, 41(1): 200-209.

[3]SLIEKERRC,BOSSD,GOEMANJJ,etal.Identificationandsystematicannotationoftissue-specificdifferentiallymethylatedregionsusingtheIllumina450karray[J].Epigenetics&Chromatin, 2013, 6(1): 1-12.

[4]ONGML,HOLBROOKJD.NovelregiondiscoverymethodforInfinium450KDNAmethylationdatarevealschangesassociatedwithaginginmuscleandneuronalpathways[J].AgingCell, 2014, 13(1): 142-155.

[5]ZHANGY,ZHANGJ.Identificationoffunctionallymethylatedregionsbasedondiscriminantanalysisthroughintegratingmethylationandgeneexpressiondata[J].MolecularBioSystems, 2015, 11(7): 1786-1793.

[6]ALISCHRS,BARWICKBG,CHOPRAP,etal.Age-associatedDNAmethylationinpediatricpopulations[J].Genomeresearch, 2012, 22(4): 623-632.

[7]HEYNH,LIN,FERREIRAHJ,etal.DistinctDNAmethylomesofnewbornsandcentenarians[J].ProceedingsoftheNationalAcademyofSciences, 2012, 109(26): 10522-10527.

[8]TROYANSKAYAO,CANTORM,SHERLOCKG,etal.MissingvalueestimationmethodsforDNAmicroarrays[J].Bioinformatics, 2001, 17(6): 520-525.

[9]BOLSHAKOVAN,AZUAJEF.Clustervalidationtechniquesforgenomeexpressiondata[J].Signalprocessing, 2003, 83(4): 825-833.

Algorithm of Identifying Differentially Methylated Region Based on Sliding Windows and KNN

LI Huabing, YANG Kun

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：In view of the shortcomings of the existing methods for identifying differentially methylated regions(DMRs), such as over deletion of sites that significance are weaker, region length limitation and can’t be directly processed by the multi-class. An algorithm of identifying DMRs based on sliding window and k-nearest neighbor(KNN) is proposed. In this method, candidate regions are obtained using sliding windows and KNN, and it merges candidate regions to get DMRs. Through real data simulation results demonstrate the method is superior to control method, such as classification performance, cluster index, the DMRs length of the control methods of Ong is extended and find some DMRs that can’t be found in control algorithm of Ong．

Key words：differentially methylated regions; slide window; k-nearest neighbor classifier; multi-class problem; cluster index

DOI：10.13954/j.cnki.hdu.2016.04.008

收稿日期：2015-11-20

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(60903086)

作者簡(jiǎn)介：李華兵(1991-)男，安徽蕪湖人，碩士研究生，數(shù)據(jù)挖掘.通信作者：楊昆副教授,E-mail: yangkun@hdu.edu.cn.

中圖分類號(hào)：TP391.4

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001-9146(2016)04-0035-05