[發明專利]用于序列設計的系統和方法

在審

• 申請號: 202210167835.0
• 申請日: 2022-02-23
• 公開（公告）號: CN114974428A
• 公開（公告）日: 2022-08-30
• 發明（設計）人: 張賀;張亮;李子煜;劉凱波;劉博翔;大衛H.馬修斯;黃亮
• 申請（專利權）人: 百度(美國)有限責任公司
• 主分類號: G16B30/20
• 分類號: G16B30/20;G16B50/40
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 杜月

1.一種用于序列設計的計算機實現的方法，包括：

接收包括多個源序列單元的源序列；

為多個源序列單元中的每個構建單元確定性有限自動機(DFA)，每個單元DFA包括多個節點，多個節點包括開始節點和結束節點，每個DFA在開始節點和結束節點之間具有一個或多個路徑，每個路徑包括多條邊，每條邊耦接在兩個相鄰節點之間；

將多個源序列單元的至少單元DFA連接成單個DFA，表示翻譯成源序列的候選靶序列；

將單個DFA與上下文無關文法(CFG)相交作為相交CFG；

定義相交CFG中的每個非終止符和開始符號；

定義相交CFG中的一個或多個規則；以及

在相交CFG中搜索具有使目標函數最小化的序列結構的期望靶序列。

2.根據權利要求1所述的計算機實現的方法，其中，所述CFG是隨機CFG(SCFG)。

3.根據權利要求1所述的計算機實現方法，其中所述源序列是包括多個氨基酸的蛋白質序列，所述候選靶序列是翻譯成所述蛋白質序列的信使核糖核酸(mRNA)序列，每個mRNA序列包含多個密碼子。

4.根據權利要求3所述的計算機實現的方法，其中，所述目標函數包括靶序列的最小自由能(MFE)和附加正則化項，所述附加正則化項是遍歷所述靶序列的全路徑的總成本。

5.根據權利要求4所述的計算機實現的方法，其中所述總成本是所述靶序列上所有密碼子的組合邊成本的總和，每個組合邊成本與所述靶序列上的密碼子相關聯。

6.根據權利要求5所述的計算機實現方法，其中所述密碼子的組合邊成本通過以下方式獲得：

對于與所述密碼子相關的氨基酸，獲得翻譯成氨基酸的所有密碼子的頻率；

將密碼子的頻率與所有密碼子中最高頻率的相對比值作為密碼子的密碼子適應指數(CAI)；以及

通過對CAI執行對數操作來獲得密碼子的組合邊成本。

7.根據權利要求1所述的計算機實施方法，其中在相交CFG中搜索具有使目標函數最小化的序列結構的期望靶序列，包括：

初始化第一哈希表以存儲單個DFA中兩個節點之間每個狀態的最佳分數，并初始化第二哈希表以存儲每個狀態的最佳反向指針；

為每個相鄰節點對的狀態初始化單例；

當在相交CFG中搜索到當前節點時，

當兩個節點之間的節點數差大于預定值時，對當前節點之前的兩個節點之間的每個狀態進行一個或多個配對規則以進行狀態更新；

對當前節點之前的兩個節點之間的每個狀態進行一個或多個分叉規則以進行狀態和反向指針更新；

保留預定數量的狀態并刪除其余狀態；以及

在相交CFG中搜索到單個DFA中的最后節點之后至少回溯期望靶序列。

8.根據權利要求7所述的計算機實現的方法，其中在所述相交CFG中搜索到所述單個DFA中的最后節點之后至少回溯期望靶序列進一步包括：

以排序順序回溯多個頂部靶序列。

9.一種用于序列設計的計算機實現的方法，包括：

接收包括多個源序列單元的源序列；

為每個源序列單元構建單元確定性有限自動機(DFA)，每個單元DFA包括多個節點，多個節點包括開始節點和結束節點，每個DFA在開始節點和結束節點之間有一個或多個路徑，每條路徑代表靶序列單元并且包括多條邊，每條邊耦接在兩個相鄰節點之間，每條路徑與遍歷所述路徑的組合邊成本相關聯；

將多個源序列單元的至少單元DFA連接成單個DFA，表示翻譯成源序列的候選靶序列，每個靶序列包括多個源序列單元；

將單個DFA與上下文無關文法(CFG)相交作為相交CFG；

在相交CFG中搜索候選靶序列中的期望靶序列，期望靶序列具有最小化目標函數的序列結構。