[發明專利]一種測序序列映射方法及系統

有效

• 申請號: 201310282312.1
• 申請日: 2013-07-05
• 公開（公告）號: CN103336916A
• 公開（公告）日: 2013-10-02
• 發明（設計）人: 李雷;王安琪;陳士劍
• 申請（專利權）人: 中國科學院數學與系統科學研究院
• 主分類號: G06F19/18
• 分類號: G06F19/18
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 宋焰琴

1.一種測序序列映射方法，對于所獲取參考基因組和至少一個測序序列進行操作；其中，參考基因組為已完成測序的基因組序列；操作包括以下步驟：

步驟1、對所述參考基因組進行預處理，以生成參考基因組壓縮結構、地址索引結構和等分點索引結構；所述參考基因組壓縮結構以壓縮形式存儲整個參考基因組，所述地址索引結構按照一定次序存儲所述參考基因組中所有子序列的地址值，所述等分點索引結構用于存儲一部分地址值在地址索引結構中所處的位置，用于加速實現測序序列的初步定位；

步驟2、基于參考基因組的特征、測序序列的整體信息、測序序列所屬物種的多態發生情況，根據概率計算，設計映射算法的參數，以達到或折中對靈敏度、特異度、映射速度的要求；

步驟3、根據經過預處理后得到的上述三種結構，通過子序列定位、基于自匹配函數的延拓、定量分析步驟將每一個測序序列映射至所述參考基因組上；

步驟4、輸出每個測序序列的映射信息。

2.如權利要求1所述的測序序列映射方法，其特征在于，步驟1中在生成參考基因組壓縮結構、地址索引結構時，將表示參考基因組的堿基字符集合{A，C，G，T}按照一定的二進制編碼規則映射至二進制表示集合{00，01，10，11}中的二進制碼；其中，對于非甲基化數據的映射，所述編碼規則指：

所述堿基字符集合{A，C，G，T}與二進制表示集合{00，01，10，11}中元素之間一一對應的映射方式。

3.如權利要求2所述的測序序列映射方法，其特征在于，所述編碼規則通過如下步驟確定：

步驟11、在堿基字符集合{A，C，G，T}與二進制表示集合{00，01，10，11}之間的每一種映射方式下，將參考基因組中每一個n位子序列映射成二進制數，該二進制數即為該n位子序列的堿基值，n為預先設定的子序列長度；

步驟12、將所述每一種映射方式下的n位子序列的堿基值序列，按順序排序，將最接近均勻分布的堿基值序列對應的映射方式作為所述編碼規則。

4.如權利要求1所述的測序序列映射方法，其特征在于，步驟1中參考基因組壓縮結構如下生成：

依照二進制編碼規則，利用二進制碼將參考基因組序列按照從左到右，或者從右到左的方向逐位存入到一個字節類型的向量中，每個字節存儲四個堿基。

5.如權利要求1所述的測序序列映射方法，其特征在于，步驟1中地址索引結構如下生成：

對于參考基因組中的每一個n位子序列按照二進制編碼規則獲得其堿基值，并按順序對每一個n位子序列的堿基值進行排序，排序后的每一個堿基值所對應的n位子序列在參考基因組中的地址值形成的序列為所述地址索引結構；其中，n為預設的參考基因組中子序列的長度。

6.如權利要求1所述的測序序列映射方法，其特征在于，步驟1中等分點索引結構如下生成：

對于區間[0，4ⁿ-1]中的等分點z_i＝i×2^2n-c，i＝0，1，2...，2^c-1，比較所述等分點z_i與地址索引結構中每個地址值對應的n位子序列的堿基值，找到一個地址值或者兩個相鄰地址值，使得該等分點z_i等于該一個地址值所對應的n位子序列的堿基值或者位于該兩個相鄰地址值所對應的n位子序列的堿基值之間，并將該一個地址值在地址索引結構中的索引值或該兩個相鄰地址值在地址索引結構中的較小索引值存儲為該等分點索引結構的第i個值，最終得到等分點索引結構。

其中c為預先設定的整數值，其取值范圍1≤c≤2n，n為預設的參考基因組中子序列的長度。

7.如權利要求1所述的測序序列映射方法，其特征在于，步驟2中所述參數包括完全匹配前綴子序列長度下界k₀和檢驗水平α，步驟1中構造地址索引結構所用的參考基因組中子序列的長度n大于k₀，k₀和檢驗水平α的選擇滿足對映射的靈敏度和特異度的要求，參數選擇依賴于參考基因組的長度、多態率和堿基頻率，測序序列長度和質量值，通過概率計算進行選擇。