一種基于BLAST的多種遺傳標(biāo)記序列比對(duì)方法＊

趙釗，王彤，孫潔，周勤虎，劉亞楠，胡蓉

（公安部物證鑒定中心，北京100038；法醫(yī)遺傳學(xué)公安部重點(diǎn)實(shí)驗(yàn)室，北京100038）

一種基于BLAST的多種遺傳標(biāo)記序列比對(duì)方法＊

趙釗，王彤，孫潔，周勤虎，劉亞楠，胡蓉

（公安部物證鑒定中心，北京100038；法醫(yī)遺傳學(xué)公安部重點(diǎn)實(shí)驗(yàn)室，北京100038）

設(shè)計(jì)并實(shí)現(xiàn)了一種基于BLAST（Basic Local Alignment Search Tool）的生物序列比對(duì)方法，它可以應(yīng)用于法庭科學(xué)多種遺傳標(biāo)記的檢索比對(duì)。引入BLAST算法并設(shè)計(jì)合理的打分函數(shù)，使其在兼容序列多態(tài)性比如線粒體DNA比對(duì)的同時(shí)，可以有效地進(jìn)行長(zhǎng)度多態(tài)性比如常染色體STR的比對(duì)。實(shí)驗(yàn)表明，采用這種方法可以實(shí)現(xiàn)不同序列的有效比對(duì)，輸出準(zhǔn)確的有序結(jié)果集，具有較高的比對(duì)效率。

法庭科學(xué)DNA數(shù)據(jù)庫(kù)；檢索比對(duì)；局部序列比對(duì)算法；序列多態(tài)性

近年來(lái)，法庭科學(xué)DNA檢驗(yàn)在方法學(xué)層面上已經(jīng)逐漸趨于成熟和穩(wěn)定，在應(yīng)用層面上已為社會(huì)普遍接受。法庭科學(xué)DNA數(shù)據(jù)庫(kù)的建設(shè)應(yīng)用也取得了令人矚目的成效，數(shù)據(jù)量增長(zhǎng)趨勢(shì)明顯。法庭科學(xué)DNA數(shù)據(jù)庫(kù)作為集成現(xiàn)代DNA檢驗(yàn)技術(shù)、信息技術(shù)和科學(xué)管理等要素，實(shí)現(xiàn)跨時(shí)空多元化應(yīng)用、精確打擊犯罪的武器，破案整體效益日益突出[1-4]。隨著DNA檢驗(yàn)技術(shù)的發(fā)展，越來(lái)越多的序列多態(tài)性數(shù)據(jù)逐漸被應(yīng)用于實(shí)踐[5-6]，尤其是針對(duì)重大疑難案件的深度研判，需要設(shè)計(jì)一種適用于多種遺傳標(biāo)記的通用比對(duì)算法。這樣既可以作為現(xiàn)有DNA數(shù)據(jù)庫(kù)檢索的有益補(bǔ)充，也符合DNA檢驗(yàn)與應(yīng)用的整體發(fā)展趨勢(shì)。

1 相關(guān)技術(shù)

1.1 序列比對(duì)

序列比對(duì)主要應(yīng)用于DNA或蛋白質(zhì)的相似性比對(duì)上，是生物信息學(xué)中的重要內(nèi)容，也是生物數(shù)據(jù)庫(kù)的基礎(chǔ)。進(jìn)行序列比對(duì)的算法主要有全局比對(duì)算法和局部比對(duì)算法以及在二者基礎(chǔ)上的改進(jìn)算法[7-8]。1990年由Altschul等人發(fā)布的基于局部序列比對(duì)的BLAST（Basic Local Alignment Search Tool）序列檢索工具，采用短片段匹配算法和一種有效的統(tǒng)計(jì)模型，可以找出目的序列與數(shù)據(jù)庫(kù)之間的最佳局部比對(duì)效果[9-10]。該算法具有較快的比對(duì)速度和較高的比對(duì)精度，在速度上比只使用動(dòng)態(tài)規(guī)劃大約快50倍左右，逐漸成為現(xiàn)今最為流行的數(shù)據(jù)庫(kù)搜索算法之一，被廣泛應(yīng)用于解決蛋白質(zhì)DNA序列的分析問(wèn)題[11]。例如最著名的NCBI（美國(guó)國(guó)立生物技術(shù)信息中心）重點(diǎn)開(kāi)發(fā)的GenBank DNA序列數(shù)據(jù)庫(kù)便利用BLAST進(jìn)行相似搜索。BLAST能夠在15 s的時(shí)間內(nèi)對(duì)整個(gè)DNA數(shù)據(jù)庫(kù)執(zhí)行序列搜索，同時(shí)，它也是EBI（歐洲生物信息研究中心）、Sanger（英國(guó)桑格研究院）等多個(gè)主要研究機(jī)構(gòu)常用的生物信息數(shù)據(jù)庫(kù)的搜索工具[12]。

1.2 法庭科學(xué)DNA數(shù)據(jù)庫(kù)

從20世紀(jì)90年代初開(kāi)始，美國(guó)、英國(guó)、加拿大、法國(guó)和日本等許多發(fā)達(dá)國(guó)家和地區(qū)已經(jīng)開(kāi)始建設(shè)DNA數(shù)據(jù)庫(kù)。隨著時(shí)間的推移，DNA數(shù)據(jù)庫(kù)在刑事案件的偵破方面發(fā)揮了巨大的作用，而且發(fā)展迅猛[13-15]。我國(guó)公安機(jī)關(guān)從1999年開(kāi)始研究和應(yīng)用DNA數(shù)據(jù)庫(kù)，近幾年來(lái)取得了規(guī)模化的發(fā)展。我國(guó)的法庭科學(xué)DNA數(shù)據(jù)庫(kù)已經(jīng)容納了五千萬(wàn)以上的短串聯(lián)重復(fù)序列（short tandem repeat，STR）數(shù)據(jù)，是目前世界上最大的DNA數(shù)據(jù)庫(kù)。近年來(lái)，國(guó)內(nèi)外陸續(xù)建立了Y-STR數(shù)據(jù)庫(kù)和線粒體DNA（mtDNA）數(shù)據(jù)庫(kù)，但是，與常染色體STR數(shù)據(jù)庫(kù)比對(duì)相互獨(dú)立，并沒(méi)有多種遺傳標(biāo)記的通用比對(duì)模式[16-17]。目前，中國(guó)法庭科學(xué)DNA數(shù)據(jù)庫(kù)檢索主要針對(duì)常染色體STR進(jìn)行逐個(gè)數(shù)字的容差式精確匹配，通常多于1～2個(gè)等位基因值的容差即跳出，比對(duì)結(jié)果為有比中或無(wú)比中，比對(duì)模式單一，雖有較高的比對(duì)效率，但結(jié)果信息不夠全面。本文實(shí)現(xiàn)的方法支持不同形式的遺傳標(biāo)記數(shù)據(jù)的檢索、比對(duì)，支持相似性模糊匹配，在一些重大案件的線索排查中可以充分發(fā)揮DNA信息的作用。

2 基于BLAST的多種遺傳標(biāo)記檢索

2.1 數(shù)據(jù)準(zhǔn)備

不同遺傳標(biāo)記呈現(xiàn)的形式不同，比如常染色體STR、Y-STR是數(shù)字形式，而mtDNA是彼此不一的字母形式。本文設(shè)計(jì)的方法首先支持常染色體STR、Y-STR、mtDNA等不同遺傳標(biāo)記的統(tǒng)一字符串格式化存儲(chǔ)，以此作為檢索比對(duì)的基礎(chǔ)。實(shí)現(xiàn)的比對(duì)系統(tǒng)基于Oracle 10g完成了樣本數(shù)據(jù)庫(kù)的搭建，并實(shí)現(xiàn)了基于高效的C/C++文件流進(jìn)行序列文件的導(dǎo)入，數(shù)據(jù)舉例如表1所示。其中，Y-STR、STR各基因座之間以空格符相隔，而同一基因座雜合子等位基因值之間以“/”相隔。

表1 數(shù)據(jù)格式化存儲(chǔ)示例

2.2 BLAST算法步驟

BLAST的核心算法步驟是將需查詢的序列數(shù)據(jù)讀入內(nèi)存，然后從數(shù)據(jù)庫(kù)的第一條記錄開(kāi)始到最后一條記錄逐條與待查詢的序列進(jìn)行比較。具體步驟如下：①設(shè)置一個(gè)最小片斷長(zhǎng)度T，對(duì)查詢序列建立長(zhǎng)度為T的片段索引表。②從數(shù)據(jù)庫(kù)中查找與表中匹配的無(wú)空位片段（如果遇到空格或“/”忽略不計(jì)入）。③設(shè)定片斷匹配最小分值S，對(duì)這些片段利用動(dòng)態(tài)規(guī)劃方法進(jìn)行無(wú)空位延伸，匹配得正分，不匹配得負(fù)分，直到得到一個(gè)局部最高分，也就是高分序列片段HSP。如果得到的HSP值小于S，則舍棄此序列。同時(shí)，為了避免無(wú)限制延伸，算法規(guī)定如果片段在進(jìn)行一段延伸后發(fā)現(xiàn)此時(shí)的分值與當(dāng)前的HSP值相差超過(guò)一個(gè)設(shè)定的值D，則停止延伸。比較此時(shí)的HSP與S，決定此片斷的取舍。查詢序列的相似度由這些局部最高分片斷決定。

其中，利用動(dòng)態(tài)規(guī)劃進(jìn)行無(wú)空位延伸為BLAST的核心，相關(guān)參數(shù)設(shè)置為，最小片段長(zhǎng)度T值為11，HSP相差閾值D為4，正確匹配得分為1，錯(cuò)誤匹配得分為-2.

以mtDNA為例，長(zhǎng)度為11的初始序列片段對(duì)如下：

（初始序列片段延伸位置22，延伸分?jǐn)?shù)11）

此時(shí)，延伸位置為22，延伸分?jǐn)?shù)為11，HSP值為11，位置為22.

基于初始序列片段對(duì)向右進(jìn)行延伸，從位置22向右延伸，發(fā)現(xiàn)從第23位到第27位的延伸均匹配，延伸分?jǐn)?shù)隨著向右的擴(kuò)展在逐步增長(zhǎng)。與此同時(shí)，HSP值和位置也發(fā)生了相應(yīng)的變化，具體情況如下：

（延伸位置27，延伸分?jǐn)?shù)16）

此時(shí)，HSP值相應(yīng)變?yōu)?6，HSP位置變?yōu)?7.當(dāng)延伸至第28位時(shí)，T與C不匹配，延伸分?jǐn)?shù)變?yōu)?4.當(dāng)延伸到第28位時(shí)，HSP值保持不變?yōu)?6（位置為27），具體如下：

（延伸位置28，延伸分?jǐn)?shù)14）

此時(shí)的HSP值和位置仍然保持不變，分別為16和27；延伸分?jǐn)?shù)與HSP值的差值為16－14＝2，沒(méi)有大于HSP相差閾值D＝4，因此，繼續(xù)向右延伸。

從第29位到第31位的延伸均匹配，當(dāng)延伸到第29位時(shí)，延伸分?jǐn)?shù)為15.此時(shí)的延伸分?jǐn)?shù)小于HSP值16，并未改變HSP。同樣，當(dāng)延伸到第30位時(shí)也未改變HSP。當(dāng)延伸到第31位時(shí)，此時(shí)的延伸分?jǐn)?shù)為17，延伸分?jǐn)?shù)大于HSP值16，HSP的值和位置變?yōu)?7和31.第29位到第31位的匹配和衍生情況如下：

（延伸位置31，延伸分?jǐn)?shù)17）

此時(shí)，HSP值相應(yīng)變?yōu)?7，HSP位置變?yōu)?1.繼續(xù)向右延伸，32位到34位均不同，當(dāng)延伸到第34位時(shí)，具體延伸情況如下：

（延伸位置34，延伸分?jǐn)?shù)11）

此時(shí)的延伸分?jǐn)?shù)為11，HSP值與延伸分?jǐn)?shù)的差值為17－11＝6，差值大于HSP相差閾值D，因此，算法停止向右延伸。這時(shí)，即使后續(xù)的3個(gè)位置（第35到第37位）均匹配，也不再進(jìn)行向右的延伸。在以上延伸過(guò)程中，延伸分?jǐn)?shù)、延伸位置和HSP的變化情況如表2所示。

至此，算法完成了向右延伸。最終的延伸位置為31，HSP值為17.向左的延伸同向右的步驟。

表2 BLAST延伸過(guò)程中的數(shù)據(jù)變化

2.3 打分機(jī)制

根據(jù)以上算法步驟逐一比對(duì)后，需要設(shè)立打分機(jī)制實(shí)現(xiàn)最終的檢索結(jié)果排序。在匹配算法的過(guò)程中，用打分函數(shù)控制整個(gè)匹配過(guò)程。本文通過(guò)分析mtDNA、STR和YSTR的特征，設(shè)計(jì)了相關(guān)的打分函數(shù)。

針對(duì)mtDNA，對(duì)于序列Si和Sj，打分函數(shù)Score（Si，Sj）定義如下：

式（1）中：α為序列中匹配字符的數(shù)量；R為匹配字符獎(jiǎng)勵(lì)的分?jǐn)?shù)（即R≥0）；β為序列中不匹配字符的數(shù)量；P為不匹配字符懲罰的分?jǐn)?shù)（P≤0）。

對(duì)于小節(jié)2.2中BLAST的動(dòng)態(tài)規(guī)劃無(wú)空位延伸中的例子，當(dāng)延伸位置為31時(shí)，R＝1，P＝－2，α＝19，β＝1，此時(shí)的分?jǐn)?shù)為α×R＋β×P＝19×1＋1×（－2）＝17.

針對(duì)STR和YSTR，根據(jù)其數(shù)字型的類型，項(xiàng)目定制了如下打分函數(shù)。對(duì)于長(zhǎng)度為n的序列，Si和Sj分別為：Si＝｛Si1，Si2…Sik…Sin｝，Sj＝｛Sj1，Sj2…Sjk…Sjn｝.

2.4 實(shí)驗(yàn)結(jié)果

實(shí)現(xiàn)基于BLAST的多種遺傳標(biāo)記序列比對(duì)系統(tǒng)，搭建實(shí)驗(yàn)數(shù)據(jù)庫(kù)，以mtDNA、YSTR、STR真實(shí)數(shù)據(jù)為基礎(chǔ)模擬批量數(shù)據(jù)進(jìn)行算法驗(yàn)證。系統(tǒng)比對(duì)結(jié)果按照匹配度從高到低返回TOP序列匹配表，同時(shí)，也可以輸出序列結(jié)果集的匹配詳情，以*標(biāo)記不同，-標(biāo)記相同。以mtDNA、STR（YSTR與STR類似）為例，結(jié)果形式見(jiàn)圖1、圖2、圖3和圖4.

圖1 mtDNA序列匹配表

圖2 mtDNA序列匹配詳情

圖3 STR序列匹配表

圖4 STR序列匹配詳情

為了提高比對(duì)效率，系統(tǒng)使用加載數(shù)據(jù)到內(nèi)存后進(jìn)行比對(duì)，以不同數(shù)據(jù)量進(jìn)行性能測(cè)試，結(jié)果見(jiàn)表3、表4、表5.

表3 mtDNA序列比對(duì)性能數(shù)據(jù)

表4 STR序列比對(duì)性能數(shù)據(jù)

表5 YSTR序列比對(duì)性能數(shù)據(jù)

3 結(jié)束語(yǔ)

應(yīng)用BLAST算法與不同打分函數(shù)實(shí)現(xiàn)對(duì)法庭科學(xué)領(lǐng)域常見(jiàn)遺傳標(biāo)記的序列檢索和結(jié)果篩選，從綜合應(yīng)用角度看，數(shù)據(jù)處理、檢索比對(duì)的性能較為理想。本文的檢索方式相比于目前中國(guó)法庭科學(xué)DNA數(shù)據(jù)庫(kù)容差比對(duì)方式，更能體現(xiàn)生物序列的匹配程度，能夠提供更為靈活和全面的有序結(jié)果集，而不是簡(jiǎn)單的有無(wú)比中。中國(guó)法庭科學(xué)DNA數(shù)據(jù)國(guó)家?guī)斐Ｈ旧wSTR數(shù)據(jù)已臻數(shù)千萬(wàn)，隨機(jī)匹配率比較高[18]，如果將本文方法應(yīng)用于STR數(shù)據(jù)的全庫(kù)比對(duì)，從效率上來(lái)說(shuō)并不適合。其應(yīng)用價(jià)值體現(xiàn)在以下2個(gè)方面：①可以就個(gè)案在小范圍（比如某地區(qū)或某年齡段）內(nèi)進(jìn)行相似度匹配檢索，以求得隱藏生物線索；②為實(shí)現(xiàn)包含多種遺傳標(biāo)記的綜合性法庭科學(xué)DNA數(shù)據(jù)庫(kù)提供算法基礎(chǔ)和檢索對(duì)照。

［1］陳連康，周懷谷，顧麗華，等.上海市公安局“法庭科學(xué)DNA數(shù)據(jù)庫(kù)”介紹［J］.刑事技術(shù)，2003（5）：3-6.

［2］侯一平，王保捷，叢斌，等.中國(guó)法醫(yī)學(xué)會(huì)物證專業(yè)委員會(huì)法醫(yī)DNA分析的若干建議［J］.中國(guó)法醫(yī)學(xué)雜志，2006，21（5）：257-259.

［3］張懷才.試述我國(guó)公安DNA數(shù)據(jù)庫(kù)在偵查中的應(yīng)用與展望［D］.上海：華東政法大學(xué)，2014.

［4］姜先華.中國(guó)DNA數(shù)據(jù)庫(kù)建設(shè)應(yīng)用技術(shù)現(xiàn)狀及發(fā)展趨勢(shì)［J］.中國(guó)法醫(yī)學(xué)雜志，2011，26（5）：383-386.

［5］王樂(lè)，葉健，白雪，等.二代測(cè)序技術(shù)及其在法醫(yī)遺傳學(xué)中的應(yīng)用［J］.刑事技術(shù)，2015，40（5）：353-358.

［6］張素華，邊英男，趙琪，等.二代測(cè)序技術(shù)在法醫(yī)學(xué)中的應(yīng)用進(jìn)展［J］.法醫(yī)學(xué)雜志，2016，32（4）：282-289.

［7］Xiong，J.Essential Bioinformatics［M］.New York：Cambridge University Press，2006.

［8］Niranjan P.Hidden Markov Models Incorporaitiong Fuzzy Measures and Integrals for Protein Sequence Identification and Alignment.Genomics Proteomics&bioinformatics，2008，6（2）：98-110.

［9］PAlexander，F(xiàn)JW Iii.Having a BLAST with bioinformatics（and avoiding BLAST phemy）.Genome Biology，2001，2（10）：1-10.

［10］李紅燕.基于BLAST算法的序列分析軟件開(kāi)發(fā)［D］.長(zhǎng)沙：中南大學(xué)，2009.

［11］SF Altschul，TL Madden，AA Sch?ffer，et al.Gapped BLAST and PSI BLAST：a new generation of protein database search programs.Nucl.Acids Res，1997（25）：3389-3402.

［12］呂軍，張穎，馮立芹，等.生物信息學(xué)工具BLAST的使用簡(jiǎn)介［J］.內(nèi)蒙古大學(xué)學(xué)報(bào)，2003，34（2）：179-186.

［13］焦文慧，宋輝.英美國(guó)家犯罪DNA數(shù)據(jù)庫(kù)建設(shè)及應(yīng)用［J］.上海公安高等專科學(xué)校學(xué)報(bào)，2013，23（2）：86-91.

［14］葛百川，王海鷗，陳連康，等.赴美考察DNA數(shù)據(jù)庫(kù)及DNA實(shí)驗(yàn)室的情況介紹［J］.刑事技術(shù)，2010（3）：3-6.

［15］趙興春，李路平，高洵.英國(guó)DNA技術(shù)應(yīng)用與國(guó)家DNA數(shù)據(jù)庫(kù)［J］.公安大學(xué)學(xué)報(bào)：自然科學(xué)版，1999（2）：17-21.

［16］劉冰.現(xiàn)階段我國(guó)DNA數(shù)據(jù)庫(kù)發(fā)展的幾個(gè)關(guān)鍵問(wèn)題［J］.刑事技術(shù)，2015，40（4）：318-323.

［17］S Montague.Global Governance of Forensic DNA Profiling and Databasing.Yale Journal of Biology& Medicine，2011，84（3）：326.

［18］葛建業(yè)，嚴(yán)江偉，Bruce Budowle，等.關(guān)于法庭科學(xué)DNA數(shù)據(jù)庫(kù)若干問(wèn)題的探討［J］.中國(guó)法醫(yī)學(xué)雜志，2011，26（3）：252-255.

D919.2

A

10.15913/j.cnki.kjycx.2017.18.001

2095－6835（2017）18－0001－04

趙釗（1984—），女，河北宣化人，助理研究員，碩士，主要研究領(lǐng)域是法庭科學(xué)DNA數(shù)據(jù)庫(kù)應(yīng)用。

〔編輯：白潔〕

公安部科技強(qiáng)警基礎(chǔ)工作專項(xiàng)項(xiàng)目“法醫(yī)DNA二代測(cè)序數(shù)據(jù)批量比對(duì)關(guān)鍵技術(shù)研究“（編號(hào)：2016GABJC18）