[發明專利]雙緩沖模型實現大規模數據庫聚類方法及系統

有效

• 申請號: 202010213789.4
• 申請日: 2020-03-24
• 公開（公告）號: CN111415708B
• 公開（公告）日: 2023-05-05
• 發明（設計）人: 劉衛國;徐曉明
• 申請（專利權）人: 山東大學
• 主分類號: G16B40/30
• 分類號: G16B40/30;G16B50/30
• 代理公司: 濟南圣達知識產權代理有限公司 37221
• 代理人: 李圣梅

1.雙緩沖模型實現大規模數據庫聚類方法，其特征是，包括：

針對基因序列數據庫進行長度遞減排序；

建立兩個緩沖區，將整個遞減排序后基因序列文件預先載入兩個緩沖區；

構建匹配字典：稀疏后綴數組，將緩沖區的一條基因序列構建稀疏后綴數組，作為字典，其它基因序列與字典后綴數組進行匹配，匹配過程中在查詢序列的某個位置采取二分查找匹配搜索，并采取逆后綴數組、最小公共子前綴數組、后綴鏈接進行處理，實現生物基因序列的聚類。

2.如權利要求1所述的雙緩沖模型實現大規模數據庫聚類方法，其特征是，在兩條序列進行相似度匹配的時候，默認較長的一條為代表序列，較短的一條為冗余序列，排序之后的第一條一定是代表序列，下邊與其相似度到達閾值的被標記為它的冗余序列。

3.如權利要求1所述的雙緩沖模型實現大規模數據庫聚類方法，其特征是，將整個基因序列文件分為多個塊，然后在內存中建立兩個緩沖區，每個緩沖區的大小和塊大小相等；

將整個基因序列文件預先載入兩個緩沖區，然后基于其中一個緩沖區中的數據進行計算操作的同時另一個緩沖區載入文件，然后進行相應的同步策略，在計算時間遠大于I/O時間的情況下，實現計算時間對I/O時間的覆蓋。

4.如權利要求1所述的雙緩沖模型實現大規模數據庫聚類方法，其特征是，設定緩沖區的大小及邊界，每個緩沖區數據的實際大小是比設定的大小界限是要大一點的，多出不到一條序列的長度。

5.如權利要求1所述的雙緩沖模型實現大規模數據庫聚類方法，其特征是，I/O操作與MEM-check的計算操作兩者之間的同步時：創建一個線程進行讀取文件到緩沖區的操作，然后創建一組線程進行MEM-check的計算工作，通過設置同步信號量full和empty來具體實現同步。

6.如權利要求1所述的雙緩沖模型實現大規模數據庫聚類方法，其特征是，針對于N條序列，創建K個線程分別進行計算，N遠大于K，每個線程計算的序列索引號為K對于N模運行取余，這樣每個線程分得的索引號是固定的。

7.如權利要求1所述的雙緩沖模型實現大規模數據庫聚類方法，其特征是，在同一個緩沖塊中的多條query序列，用最長的計算時間來掩蓋次長的計算時間，減少整體水平上的等待時間。

8.如權利要求1所述的雙緩沖模型實現大規模數據庫聚類方法，其特征是，預先將query源文件進行排序操作，使得其中的數據序列按照長度遞減排列，每個線程所分得的數據長度都是相近的，最大精確匹配算法的計算時間與query長度呈正相關，從而使得各個線程之間的運行時間相差不大，整體運行時間趨于平均時間而非最壞情況下運行時間。

9.如權利要求1所述的雙緩沖模型實現大規模數據庫聚類方法，其特征是，塊的大小為動態調度，其中每一個塊的大小僅僅設置一個參考值而不是固定大小，在讀入操作達到塊大小的情況下判斷是否讀入的序列條數為線程數目的整數倍，如若不是，繼續讀入知道滿足條數為線程數目整數倍的情況為止。

10.雙緩沖模型實現大規模數據庫聚類系統，包括存儲器、處理器及存儲在存儲器上并可在處理器上運行的計算機程序，其特征是，所述處理器執行所述程序時實現以下步驟：

針對基因序列數據庫進行長度遞減排序；

建立兩個緩沖區，將整個遞減排序后基因序列文件預先載入兩個緩沖區；

構建匹配字典：稀疏后綴數組，將緩沖區的一條基因序列構建稀疏后綴數組，作為字典，其它基因序列與字典后綴數組進行匹配，匹配過程中在查詢序列的某個位置采取二分查找匹配搜索，并采取逆后綴數組、最小公共子前綴數組、后綴鏈接進行處理，實現生物基因序列的聚類。