經(jīng)過近5年的深入研究與攻關(guān)，一個困擾數(shù)據(jù)挖掘與大數(shù)據(jù)分析領(lǐng)域40多年的經(jīng)典NP難問題（MLCS問題），在西安電子科技大學(xué)軟件學(xué)院李雁妮副教授負(fù)責(zé)的科研團隊手中從理論和算法上取得階段性突破。目前，該研究的基礎(chǔ)性與階段性成果論文：“A Novel Fast and Memory Efficient Parallel MLCS Algorithm for Long and Large-Scale Sequences Alignments”和“A Real Linear and Parallel Multiple Longest Common Subsequences (MLCS) Algorithm”已分別被數(shù)據(jù)庫與數(shù)據(jù)挖掘領(lǐng)域的A類頂級國際會議ICDE 2016及其頂級會議SIGKDD 2016全文接收錄用。
問題來源：時代的迫切需求
MLCS問題（Multiple Longest Common Subsequences for Multiple Sequences）即為求多個字符序列中的某個或者所有的最長公共子序列問題，它在基因檢測、序列相似性比對、模式識別、數(shù)據(jù)挖掘、代碼克隆檢測、文獻查重、網(wǎng)頁聚類等領(lǐng)域都有著重要而普遍的應(yīng)用。
目前求解MLCS問題通常采用上世紀(jì)70年代提出的基于動態(tài)規(guī)劃的MLCS算法，或者上世紀(jì)80年代產(chǎn)生的基于支配點的MLCS算法。而隨著大數(shù)據(jù)時代的到來，各種應(yīng)用領(lǐng)域中的字符序列的長度與規(guī)模正呈指數(shù)爆炸式增長，已有的MLCS算法已不能滿足大規(guī)?；蜉^長字符序列的比對需求。
“一般而言，任何信息都可抽象為在一個有限字符集下的字符串，”李雁妮介紹說，“例如，一個基因的DNA就是在字符集{A,C,G,T}下的一個字符序列，當(dāng)比對字符序列的規(guī)模足夠大或者長度足夠長的時候，如果不能在理論和算法上實現(xiàn)突破，那么無論在高性能計算機上，還是在大數(shù)據(jù)平臺上，求解比對字符序列的MLCS都無法在多項式時間內(nèi)計算出結(jié)果?！?/p>
被譽為“生命科學(xué)的登月計劃”的人類基因組計劃已經(jīng)開展了幾十年，而基于“生物基因序列比對”及“基因剪刀”等技術(shù)的腫瘤研究問題，受制于數(shù)據(jù)處理仍進展緩慢:據(jù)粗略測算，最長的基因序列長度已接近10的19次方，即便在高性能計算機上，使用目前最好的MLCS算法，也只能對字符集為4、序列個數(shù)為5、序列長度為300的基因字符序列進行比對。
大數(shù)據(jù)分析算法和大數(shù)據(jù)平臺的關(guān)系，就好比汽車和高速公路的關(guān)系，如果汽車本身存在缺陷或者性能低劣，則高速公路對于這輛車而言就沒有充分發(fā)揮它本身應(yīng)有的“高速”作用。“我們要做的，就是要創(chuàng)新提出一種更優(yōu)的MLCS算法，不僅使其在時間和空間性能上實現(xiàn)突破，而且可以最終實現(xiàn)在一般機器上，對任意規(guī)模和任意長度的大字符序列以線性時間進行比對?！崩钛隳菡f。
陜公網(wǎng)安備61019002002681號
