序列是一種重要的數(shù)據(jù)類(lèi)型,在諸多應(yīng)用領(lǐng)域廣泛存在.基于序列的特征選擇具有廣闊的現(xiàn)實(shí)應(yīng)用場(chǎng)景.交互特征是指一組整體具有顯著強(qiáng)于單獨(dú)個(gè)體與目標(biāo)相關(guān)性的特征集合.從大規(guī)模序列中挖掘交互特征面臨著位點(diǎn)的"組合爆炸"問(wèn)題,計(jì)算挑戰(zhàn)性極大.針對(duì)該問(wèn)題,以生物領(lǐng)域高通量測(cè)序數(shù)據(jù)為背景,提出了一種新的基于并行處理和演化計(jì)算的高階交互特征挖掘算法.位點(diǎn)數(shù)是制約交互作用挖掘效率的根本因素.擯棄了現(xiàn)有方法基于序列分塊的并行策略,采用基于位點(diǎn)分塊的并行思想,具有天然的效率優(yōu)勢(shì).進(jìn)一步,提出了極大等位公共子序列（maximal allelic common subsequence, MACS）的概念并設(shè)計(jì)了基于MACS的特征區(qū)域劃分策略.該策略能將交互特征的查找范圍縮小至許多"碎片"空間,并保證不同"碎片"間不存在交互特征,避免計(jì)算耦合引起的高額通信代價(jià).利用基于置換搜索的并行蟻群算法,執(zhí)行交互特征選擇.大量真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,證實(shí)提出的PACOIFS算法在有效性和效率上優(yōu)于同類(lèi)其他算法. 

【文章來(lái)源】：計(jì)算機(jī)研究與發(fā)展. 2019,56(05)北大核心EICSCD

【文章頁(yè)數(shù)】：15 頁(yè)

【部分圖文】：

圖１極大等位公共子序列的示例圖Ｆｉｇ．１Ａｎｅｘａｍｐｌｅｏｆｍａｘｉｍａｌａｌｌｅｌｉｃｃｏｍｍｏｎｓｕｂｓｅｑｕｅｎｃｅ

ｍ，１≤ｊ≤ｔ，發(fā)現(xiàn)：所有滿(mǎn)足定義３，與特定類(lèi)標(biāo)簽ｃｒ∈Ｃ存在顯著統(tǒng)計(jì)關(guān)聯(lián)的ｋ階交互特征并且滿(mǎn)足ＦＷＥＲ≤α．３ＰＡＣＯＩＦＳ框架第２．１節(jié)所述，大規(guī)模生物序列中的高階交互特征挖掘面臨著密集計(jì)算問(wèn)題．本節(jié)將提出一種新的基于并行處理和演化計(jì)算的解決框架（ＰＡＣＯＩＦＳ），并對(duì)構(gòu)成框架的各主要步驟加以詳細(xì)介紹．３．１整體思想圖２給出了ＰＡＣＯＩＦＳ框架的總體示意圖：Ｆｉｇ．２ＡｎｉｌｌｕｓｔｒａｔｉｏｎｏｆＰＡＣＯＩＦＳ圖２ＰＡＣＯＩＦＳ框架示意圖框架由４個(gè)主要步驟構(gòu)成：１）數(shù)據(jù)預(yù)處理．對(duì)原始數(shù)據(jù)進(jìn)行編碼后，執(zhí)行特征維度削減，提前過(guò)濾一些無(wú)關(guān)特征，提高整個(gè)框架的執(zhí)行效率．２）數(shù)據(jù)劃分．基于極大等位公共子序列ＭＡＣＳ，將原始高維特征數(shù)據(jù)劃分成一系列低維特征區(qū)域，并保證其“低耦合高內(nèi)聚”性（即特征交互在區(qū)域內(nèi)的可能性高，在區(qū)域間的可能性低）．３）特征區(qū)域篩選．許多劃分后的特征區(qū)域具有較高的相似度．如果在所有特征區(qū)域上都執(zhí)行交互趙宇海等：一種面向大規(guī)模序列數(shù)據(jù)的交互特征并行挖掘算法５９９

可能的“熱區(qū)”．其問(wèn)題在于，單位點(diǎn)過(guò)濾大多只保留具有強(qiáng)邊際效應(yīng)的候選位點(diǎn)，許多具有弱邊際效應(yīng)但具有強(qiáng)交互作用的位點(diǎn)組合被遺漏了．在對(duì)原始數(shù)據(jù)編碼后，本節(jié)中將提出一種結(jié)合塊過(guò)濾和位點(diǎn)過(guò)濾的２階段過(guò)濾方法ＢＬＦｉｌｔｅｒ．先通過(guò)基于圖論的塊過(guò)濾，粗粒度地保留與疾病具有較高關(guān)聯(lián)可能性的區(qū)域；再通過(guò)細(xì)粒度的位點(diǎn)過(guò)濾進(jìn)一步提煉保留區(qū)域內(nèi)的位點(diǎn)，以最大限度地保留邊際效應(yīng)弱但交互作用強(qiáng)的位點(diǎn)．Ｆｉｇ．３Ｔｈｅｇｒａｐｈｍｏｄｅｌｏｆｂｌｏｃｋｓ圖３分塊的圖模型３．２．１塊過(guò)濾塊過(guò)濾階段，輸入序列被劃分為??－Ｎ??ｋ?－塊．其中，前??－Ｎ??ｋ?－－１塊每塊包含ｋ個(gè)位點(diǎn)，最后一塊包含Ｎ－ｋ×??－Ｎ??ｋ??（－１）個(gè)位點(diǎn)．根據(jù)劃分后塊內(nèi)和塊間存在的顯著交互位點(diǎn)對(duì)的數(shù)量，可構(gòu)建如圖３所示的無(wú)向權(quán)重圖Ｇ＝（Ｖ，Ｅ）．其中，第ｉ個(gè)序列塊對(duì)應(yīng)頂點(diǎn)ｖｉ∈Ｖ．如果第ｉ個(gè)序列塊和第ｊ個(gè)序列塊之間存在顯著交互的位點(diǎn)對(duì)，則存在邊ｅｉｊ∈Ｅ．頂點(diǎn)ｖｉ的權(quán)重ｗｉ為塊ｉ內(nèi)顯著交互的位點(diǎn)對(duì)數(shù)，邊ｅｉｊ的權(quán)重ｗｉｊ為塊ｉ和塊ｊ之間的顯著交互位點(diǎn)對(duì)數(shù)．對(duì)給定的頂點(diǎn)集合Ｖ′?Ｖ，若記其在Ｇ中對(duì)應(yīng)的導(dǎo)出子圖為Ｇ′，則可定義Ｇ′的密度為ｄ（Ｇ′）＝∑ｉ，ｊ∈Ｇ′∧ｉ＜ｊｗｉｊ＋∑ｋ∈Ｇ′ｖｋＳＧ′，（１）其中，ＳＧ′＝｜ＶＧ′｜＋｜ＶＧ′｜（｜ＶＧ′｜－１）２?


本文編號(hào)：3382412