《生物序列大數據集模體發現算法的研究》是依託西安電子科技大學，由於強擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：生物序列大數據集模體發現算法的研究
- 項目類別：青年科學基金項目
- 項目負責人：於強
- 依託單位：西安電子科技大學
中文摘要,結題摘要,
中文摘要
模體發現對生物序列中定位有意義的序列片斷起著非常重要的作用。模體發現的精確算法能在指定測度下找出輸入序列中最優的模體，但近年來生物序列大數據集為精確算法在時間性能方面提出了新的挑戰。本項目採用基於模式驅動的技術路線進行模體發現，以設計時間高效的模體發現的精確算法為基本目標，並分別從減少候選模體和加速候選模體驗證兩個角度確保算法具有高效的時間性能。首先，建立在大的序列數據集中選擇參考序列的方法，使選出的參考序列在所有可能的參考序列中對應最小數量的候選模體；其次，建立占用存儲空間小的由三個子串生成候選模體的方法，使得進一步減小候選模體的數量；最後，設計時間高效的模體驗證算法，使在長度為n的序列上驗證長度為l的候選模體的時間性能達到O(nl/log(n))。本項目所設計的精確算法將能夠在含有數百條甚至更多序列的生物序列大數據集中快速地進行模體發現。
結題摘要
(1) 項目的背景 模體發現對生物序列中定位有意義的序列片斷起著非常重要的作用，但近年來生物序列大數據集為模體發現帶來了巨大的計算挑戰。設計適用於生物序列大數據集的時間高效的模體發現算法是當前模體發現領域的一個重要任務，有助於在基因組水平探索基因的表達調控機制。 (2) 主要研究內容 針對生物序列大數據集下的模體發現問題，本項目圍繞精確的模體發現算法，主要展開了如下研究：選擇恰當的參考序列對已有精確算法進行加速；設計已有精確算法適配大數據集的版本；設計高效的基於模式驅動的大數據集精確算法；設計大數據集模體發現的樣本序列選擇算法；研究已識別模體的時空互動關係。 (3) 重要結果 建立了模式驅動的模體識別算法的參考序列選擇問題，提出了一個稱為RefSelect的算法來快速地選取生成少的候選模體的參考序列，可以使現有精確算法的時間性能提升多達100倍。通過提取和合併序列中的相似子串，提出了精確算法PairMotif的適配大數據集的版本PairMotifChIP。充分分析了模式驅動的模體發現算法的計算複雜度，並設計了適用於DNA序列大數據集的模式驅動的精確算法PTMotif，時間性能顯著地優勝於當前最好的精確算法。建立了模體發現的樣本序列選擇問題，並設計了樣本序列選擇算法，使得現有精確算法運行於選出的樣本序列時使用很短的時間便能成功地找出模體。 (4) 關鍵數據及科學意義 我們在本領域重要期刊BMC Bioinformatics等和重要會議IEEE International Conference on Bioinformatics and Biomedicine (CCF B類會議)等發表了8篇論文，其中6篇為期刊論文，2篇為會議論文，SCI檢索5篇，EI檢索3篇。開發了可在GitHub或Google上訪問的軟體。這些研究成果為進一步研究具有複雜結構的模體的識別以及超大規模序列數據集上模體的搜尋與識別奠定了較好的基礎。
