[發明專利]基于K-means聚類的多元宇宙算法的DNA存儲編碼優化方法

有效

• 申請號: 201910796324.3
• 申請日: 2019-08-27
• 公開（公告）號: CN110533096B
• 公開（公告）日: 2021-09-10
• 發明（設計）人: 王賓;曹犇;周士華;張強;魏小鵬
• 申請（專利權）人: 大連大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/12
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 畢進

本發明公開了基于K?means聚類的多元宇宙算法的DNA存儲編碼優化方法，其具體為：構造滿足組合約束條件的最優DNA編碼序列，首先要構造出一定個數的DNA序列作為初始種群，對種群的適應度進行評價排序。其次，利用已經得出的DNA編碼序列，用k均值聚類算法和蟲洞交叉進行優化，得到適應度較高的DNA編碼序列。然后，通過約束比對根據約束判斷是否加入備選解集合。最后，輸出最優DNA編碼序列。該方法可以搜索出數量較優的DNA編碼序列。

技術領域

本發明涉及群體智能優化算法和DNA存儲編碼，具體來說是用多元宇宙算法、K-means聚類算法和蟲洞交叉來優化DNA編碼序列，其屬于DNA存儲中編碼設計領域。

背景技術

DNA存儲技術最早被認為是Joe Davis發起的Microvenus project，目的是在DNA中存儲圖像等非生物數據。編碼基于CTAG的堿基分子大小(C-1、T-2、A-3、G-4)，四個堿基被分配為相變值而不是增量值。每個堿基表示每個二進制位(0或1)轉換為另一個二進制要進行多少次重復變換，這是計算機壓縮存儲的一種技術。或可表示為，C＝X、T＝XX、A＝XXX、G＝XXXX。例如，10101→CCCC，100101→CTCCT。然而在解碼時就出現了一個問題，C可以解碼成0或1就導致了很多錯誤。這種方法是DNA存儲編碼方面的先驅，但是因為解碼前后的不一致容易產生錯誤而沒有得到廣泛的應用。DNA存儲在保存時間上具有優勢，在適應的條件下DNA數據存儲可以保存多年。然而，讀寫DNA數據的成本依然很高。但是最近DNA合成和測序方法的飛速發展,DNA存儲在將來會是一個很有競爭力的存儲解決方案。

發明內容

本申請提出了基于K-means聚類的多元宇宙算法的DNA存儲編碼優化方法，該方法首先用多元宇宙算法對初始種群進行搜索初始解集；其次，用k均值聚類算法對多元宇宙算法得到的編碼進行聚類；接著，將聚類后得到的最劣集合和最優集合等數目交叉；最后，比對所得集合是否滿足約束條件，符合約束的加入備選解集合；該方法可以搜索出數量較優的DNA編碼序列。

為實現上述目的，本申請的技術方案為：基于K-means聚類的多元宇宙算法的DNA存儲編碼優化方法，其具體為：構造滿足組合約束條件的最優DNA編碼序列，首先要構造出一定個數的DNA序列作為初始種群，對種群的適應度進行評價排序。其次，利用已經得出的DNA編碼序列，用k均值聚類算法和蟲洞交叉進行優化，得到適應度較高的DNA編碼序列。然后，通過約束比對根據約束判斷是否加入備選解集合。最后，輸出最優DNA編碼序列。

本發明由于采用以上技術方案，能夠取得如下的技術效果：

1、用多元宇宙算法對初始種群進行適應度計算，引入黑/白洞隧道不僅可以把物質隨機傳送到最好宇宙，還可以提高初始種群的平均適應度；

2、k均值聚類算法克服多元宇宙算法前期收斂慢的缺點，加快收斂速度，使得算法有更快的迭代速度,使用蟲洞交叉可以避免算法后期陷入局部最優；

3、本發明提出的基于k均值聚類的多元宇宙算法的DNA序列優化算法能夠搜索出數量較優的DNA編碼序列。

附圖說明

圖1為本發明的實現流程圖。

具體實施方式

下面將結合本發明實施例中的附圖，對本發明實施中的技術方案進行清楚、完整的描述，可以理解的是，所描述的實例僅僅是本發明的一部分實例，而不是全部的實施例。基于本發明的實施例，本領域的技術人員在沒有做出創造性勞動的前提下所獲得的所有其他實施例，都屬于本發明的保護范圍。