SMILES表達式的子結構關系檢測算法

彭 彬，劉 釗，顧進廣

(1.武漢科技大學 計算機科學與技術學院，湖北 武漢 430065；2.武漢科技大學 智能信息處理與實時工業系統湖北省重點實驗室，湖北 武漢 430065)

0 引 言

尋找一種方法能精確簡潔地獲取化合物結構信息是化合物檢索研究領域首先需要解決的問題[1]。當前研究人員提出了許多研究方案,對結構檢索做出了較大的貢獻。其主流的研究方向有兩種，線性碼、連接表。線性碼的應用主要有SMILES編碼[2,3]和SMARTS編碼[4]，連接表的研究主要有Ullmarm算法[5]與VF算法[6]。其中基于線性碼的SMARTS編碼，作為一種有效化合物結構查詢方法，被人們廣泛使用。

SMARTS編碼結構檢索的機制是通過輸入的SMILES重構化學式，再搜索子圖的同形，而不是直接通過SMILES的對比完成的。通過對SMILES編碼改造的方式達到檢索目的，雖然搜索結果準確性較高，但這種避開分析SMILES編碼去重新構造新的編碼的方式并不能解決某些場合下的問題。如SMILES表達式可以被一些化學式編輯軟件如Marvin導入并轉換成二維圖形或三維分子模型，若判斷編輯的化學式之間的結構關系，則需要分析SMILES表達式的結構信息；再如SMILES表達式與MOL[7]文件都是存儲化合物的結構信息，且SMILES表達式能夠與MOL文件進行相互轉換，通過分析SMILES表達式之間的結構關系可以判斷MOL文件間的關系，為之后MOL文件的查找跟分類的研究提供參考。本文以上述研究為基礎，提出一種檢測SMILES表達式之間子結構關系的算法,通過分析SMILES表達式來獲取子結構關系信息。

1 算法思路

在引言中指出，一些應用場景如以SMILES作為結構信息載體的化合物結構匹配，MOL文件分類，需要通過分析SMILES表達式所包含的結構信息去獲取化合物之間的結構關系，但通過分析SMILES表達式來檢測化合物之間的結構關系，至今還沒有一種好的方法。考慮到化合物結構的特殊性和復雜性，子結構查詢中所涉及到的子串不能通過簡單的子串匹配獲取結構關系[8,9]。

針對上述問題，本文的思路是研究一種能確定SMILES表達式之間子結構關系的算法，該算法包括：定義并存儲常見原子、化學鍵和原子間的支鏈關系；定義切片最小粒度：相鄰原子與之間的化學鍵關系與支鏈關系作為最小粒度單位；定義起始原子和終止原子，其中起始原子為所述最小粒度對應的第一個原子，終止原子為所述最小粒度對應的第二個原子；基于常見原子、化學鍵和原子間的支鏈關系對獲取的SMILES表達式進行分析，將SMILES表達式切割成一個個原子對，統計SMILES表達式包含的環個數及原子對的種類、每種原子對的個數并存儲到哈希表中；根據原子對的種類、每種原子對的個數、環的個數來確定SMILES表達式之間子結構關系。

2 算法介紹

該算法的目標是確定SMILES表達式之間是否具有子結構關系。該算法包括：

(1)定義并存儲常見原子、化學鍵和支鏈關系。

(2)定義切片最小粒度：相鄰原子和原子之間的化學鍵關系以及支鏈關系三者共同決定最小粒度單位。

(3)定義起始原子和終止原子，其中起始原子為所述最小粒度對應的第一個原子；終止原子為所述最小粒度對應的第二個原子。

(4)基于常見原子、化學鍵和支鏈關系對獲取的SMILES表達式進行分析。將SMILES表達式切割成一個個原子對，統計SMILES表達式包含的環的個數及原子對的種類、每種原子對的個數并將統計結果存儲到哈希表中，其中所述原子對根據相鄰原子與之間的化學鍵關系與支鏈關系確定。

(5)根據原子對的種類、每種原子對的個數、環的個數確定SMILES表達式之間是否具有子結構關系。

算法的主要步驟、切片過程、獲取原子、匹配過程4個部分的詳細說明如下：

2.1 算法主要步驟

(1)確定常見原子、化學鍵、支鏈關系。常見的原子(Atom)：H，C，N，O，S，F，Cl，Br，[N+]，[N-]，[O+]，[O-]。常見的化學鍵(Bond)：單鍵，雙鍵，三鍵，楔型向上鍵，楔形向下鍵，離域鍵，順反不確定鍵，空心鍵，不確定鍵。

(2)分析SMILES表達式包含的信息。SMILES存儲的信息主要包含原子的種類、原子之間的化學鍵、支鏈關系。

(3)定義切片最小粒度：相鄰原子、相鄰原子之間的化學鍵與支鏈關系作為最小粒度單位。決定化學式分子式結構的主要因素有原子的種類，原子之間的化學鍵，支鏈關系。

(4)定義起始原子和終止原子。其中起始原子為所述最小粒度對應的第一個原子；終止原子為所述最小粒度對應的第二個原子。

(5)切片處理。將待匹配的SMILES表達式進行切割成一個個原子對。統計原子對的種類、個數，并存儲到哈希表中。

(6)匹配判斷。根據切片種類、切片對應的數量來判斷SMILES表達式之間是否具有子結構匹配關系。

本算法會設置3個常用的變量來存儲切片結果。分別為切片種類(Kh)，每種切片的數量(Ch)，環結構數量(circle)。

2.2 切片過程

根據算法步驟(5)中提到，需要將SMILES表達式按照預定義的最小粒度進行切割。考慮到SMILES表達式環結構是用數字表示，故切片第一步需要獲取環結構信息，去掉SMILES表達式中的數字，以簡化后續的切片過程。本文將切片過程分為兩個子步驟：獲取環結構信息，獲取切片信息。其中獲取環結構信息算法描述如下：

步驟1 預處理。因為此次匹配流程是不考慮異構SMILES情況，所以首先會對那些存儲異構 SMILES的字符串剔除異構字符。如"/"，""。

步驟2 統計環的個數與環邊拆分位置的原子對。其詳細過程如下：

(1)遍歷SMILES表達式每一個字符，觀察是否有數字字符。

(2)若包含數字，記住該數字的位置，并從該位置后繼續遍歷直到找到包含同樣數字字符，環個數加1。存儲環邊拆分位置的原子對。過濾掉這兩個位置的數字，組成新的字符串。

(3)對新組成的字符串進行遍歷尋找下一個數字。

(4)當新組成的字符串無數字字符，存儲環個數，則環個數統計結束。

算法1：獲取環結構信息

Algorithm 1getCircleInfo()

Input:

Setstr←smiles;h=0;Kh={φ};Ch={φ};circle=0

(1)str?preHandle(str)

(2)fori=0;i

(3)ifisNumber(str[i])then

(4)num=str[i]

(5)forj=i;j

(6)ifstr[i]==str[j]then

(7)ifisBond(str[j-1])then

(8)piece=getPrevAtom(str[i])+str[j-1]

(9)piece=piece+getNextAtom(str[j])

(10)ifpiece∈Kh,piece==Kh[t]then

(11)Ch[t]←Ch[t]+1

(12)else

(13)Kh+1[t]←Kh[t]∪{piece};Ch+1[t]←Ch[t]∪{φ}

(14)h←h+1

(15)endifendifendifendfor

(16)circle←circle+1

(17)endifendfor

(18)str?removeNumber(str)

Output:

str,h,Kh,Ch,circle

SMILES表達式經過算法getCircleInfo(algorithm 1)處理后，將輸出參數作為算法getPiece(algorithm 2)的輸入參數。其獲取切片信息的算法描述如下：

步驟3 對經過預處理與去環結構后的SMILES字符串進行循環遍歷，判斷str[i]的值情況。

步驟4 若為"="，則化學鍵="="。起始原子為該位置前的第一個原子，終止原子為該位置后的第一個原子。

步驟5 若為"#"，則化學鍵="#"。起始原子為該位置前的第一個原子，終止原子為該位置后的第一個原子。

步驟6 若為"("，該位置前的第一個原子也就是起始原子與左括號內的內容，組成新的字符串，設置為str1；起始原子與對應右括號后的內容，組成str2；將str1，str2作為新的 SMILES表達式進行切片流程處理。此方式運用的迭代算法。

步驟7 若為")"，位置指針向左尋找，找到與該括號匹配的左括號位置，并將左括號左邊的第一個原子作為起始原子，位置為起始位置。

步驟8 若為其它字符，則化學鍵=""。起始原子為該位置前的第一個原子，終止原子為該位置后的第一個原子。

步驟9 根據原子對=startAtom+bond+stopAtom，得到原子對的值，并存儲到哈希表中。

步驟10 將此次切片結果存儲到哈希表中，key值為片段名，value存儲為該片段的個數。切片結果展示的是SMILES結構式被切片后的切片種類與每種切片對應的個數。

算法2：切片過程

Algorithm 2getPiece()

Input:

Setstr,h,Kh,Ch,circlefromgetCircleInfo()

(1)fori=0;i

(2)ifstr[i]=="("then

(3)str←s1(s2)s3;getPiece(s1(s2));getPiece(s1s3)

(4)elseifstr[i]==")"then

(5)i←i+1

(6)else

(7)ifstr[i]=="#"‖str[i]=="="then

(8)bond←str[i]

(9)end if

(10)startAtom,start?getPrevAtom(i)

(11)stopAtom,stop?getNextAtom(start)

(12)i←stop;piece=startAtom+bond+stopAtom

(13)ifpiece∈Kh,piece==Kh[t]then

(14)Ch[t]←Ch[t]+1

(15)else

(16)Kh+1[t]←Kh[t]∪{piece};Ch+1[t]←Ch[t]∪{φ}

(17)h←h+1

(18)endifendifendfor

Output:

str,Kh,Ch,circle

2.3 獲取原子

切片過程中有提到獲取起始原子，終止原子的方法，也就是算法偽代碼中的getPrevAtom()，getNextAtom()。本小節將對SMILES表達式中獲取指定位置原子的過程做詳細說明。獲取SMILES表達式對應位置i的原子公式如下

步驟1 從起始位置對應的字符進行判斷，將常用的雙原子列表存入配置文件中。其中常見的雙原子有Br,Cl。

步驟2 判斷是否為雙原子。位置i的字符設置為ch1，若ch1對應雙原子第一個字符，且位置i+1的字符ch2對應雙原子第二個字符，則起始原子=ch1+ch2。若不是，則起始原子=ch1。

步驟3 判斷是否為括號。若為括號，當前位置加1，繼續對新的字符判斷。

步驟4 判斷是否存在離子。若存在"["字符，則繼續尋找直到遇到"]"字符。則"["與"]"之間組成的字符串即為起始原子，起始原子="["+ch1+...+chi+...+chn+"]"。

2.4 匹配過程

獲取切片結果集后，需要根據切片結果集進行匹配檢測。匹配方式如圖1所示。將兩個待匹配的SMILES表達式進行切片處理，待匹配的SMILES表達式切片結果記為A,被匹配的SMILES表達式結果記為B。將A跟B的結果進行比較：

步驟1 若A的環個數大于B的環個數，則匹配不成功，不具有子結構關系。

步驟2 若A種類大于B種類，則匹配不成功，不具有子結構關系。

步驟3 若A每種切片個數大于B對應切片個數，則匹配不成功，不具有子結構關系。

步驟4 不滿足上述條件時，匹配成功，具有子結構關系。

圖1 SMILES匹配流程

3 實驗與評估

本文的實驗數據是參照《合成香料技術手冊》[10]提到的1001種合成香料，根據CAS[11]編號從相關化工站點中抓相關香料信息，其中包含SMILES表達式的香料有638種。本文從ChemNet網中抓取638條化工香料，存儲到xml文檔中，文檔中數據共包含638種CAS號，每種CAS號對應著一種SMILES表達式，其中數據的來源分布見表1。

表1 化工香料數據的種類

實驗分成兩個過程：①檢查香料切片的準確性；②將香料的子結構與香料結構進行對比，檢測匹配的準確性。判斷SMILES表達式之間結構關系的準確性滿足式(1)

AR=SR*MR

(1)

其中，AR為子結構準確率，SR為切片的準確率，MR為匹配的準確率。

3.1 切片實驗

將抓取后的638種化工香料進行算法切片，存儲每種香料的切片結果。同時將這些切片進行人工切片處理，將切片處理結果跟算法切片結果進行對比，若算法切片跟人工切片結果相同，則切片準確。如對香料檀香210進行切片處理，按照切片定義，最小切片種類有CC,C(C),C=C,circle。其中CC代表起始原子與終止原子均為碳原子，原子之間以單鍵相連；C(C)代表起始原子與終止原子為碳原子。原子之間以單鏈相連，并具有支鏈關系；C=C代表起始原子與終止原子為碳原子。原子之間以雙鏈相連；circle代表此香料化學式擁有環狀結構的個數。切片結果見表2。

根據切片結果可知，算法切片將該化合物SMILES切割成CC，C(C)，C=C，C=O這4種片段，具有circle結構，個數分別為8，5，1，1，1。算法切片跟人工切片結果一致，故可判定對香料檀香210進行切片處理準確。經過實驗，對638種香料進行切片處理，其提取出的信息總條數為638，提取出的正確信息條數為636，根據處理式(2)求出切片正確率=636/638=99.7%

表2 檀香210的切片結果

SR=CI/TI

(2)

其中，CI為提取正確信息條數，TI為提取信息總條數。

3.2 匹配實驗

再從638條香原料中隨機抽取50條香料數據做匹配實驗，通過對每一條香料可能存在的子結構與此香料結構進行匹配驗證。匹配的正確性是通過將每一條香料子結構的SMILES與該香料結構的SMILES進行匹配檢測，若匹配成功則具有子結構關系。如對3-蒈烯進行匹配實驗，首先對該化合物進行切片處理，切片結果見表3；再對3-蒈烯可能存在的子結構進行切片處理，切片結果見表4。將子結構的切片結果與3-蒈烯的切片結果進行對比，通過匹配算法判斷是否匹配，進而驗證這個子結構與該化合物的匹配關系，實驗數據見表4。

表3 3-蒈烯切片結果

表4 3-蒈烯子結構的匹配結果

根據匹配結果可知，3-蒈烯所有可能子結構的SMILES與該香料結構的SMILES進行匹配檢測，3-蒈烯所包含的子結構按照圖1匹配算法得出的結論是匹配的。經過實驗，50種香料共計928種子結構。匹配正確的條數921條，錯誤條數7條。根據處理式(3)求出匹配準確率=921/928=99.2%

MR=CI/TI

(3)

3.3 實驗結論

根據切片實驗跟匹配實驗的結果可知，切片算法的準確率為99.7%，匹配算法的準確率為99.2%。根據處理式(1)得出SMILES表達式之間是否具有子結構關系的準確率為98.9%，具有很高的準確性。其中切片過程中0.3%錯誤率是因為香料存在一個CAS號對應多個SMILES表達式的情況，而本文目前只考慮的一種CAS號對應一種SMILES表達式；匹配過程0.8%的錯誤率是因為SMILES表達式中環位置標記數字是相同的，代表著環之間不交叉，如表達式C1CC1C1CC1。本算法中考慮的是SMILES表達式中每種環位置的標記數字是不同的。

4 結束語

本文的實驗數據來自香料企業生產的1001種合成香料，以算法切片匹配做實驗組，人工切片匹配作對照組。通過實驗可知，該算法檢測SMIELS表達式之間子結構關系的準確性很高。本算法通過將SMILES表達式切割成一個個不可再分的片段，再去比較各片段的數量來判斷化學式之間是否具有子結構匹配關系，本算法可用于判斷化合物之間的結構關系。該方法簡單，匹配準確性高，可為下一步做基于SMILES結構檢索數據庫的工作做依據參考。

[1]Toropov A A,Toropova A P,Martyanov S E,et al.Comparison of SMILES and molecular graphs as the representation of the molecular structure for QSAR analysis for mutagenic potential of polyaromatic amines[J].Chemometrics and Intelligent Laboratory Systems,2011,109(1):94-100.

[2]Suzuki M,Manago N,Ozeki H,et al.Sensitivity study of SMILES-2 for chemical species[C]//Sensors,Systems,and Next-Generation Satellites XIX,2015.

[3]Brefo-Mensah E K,Palmer M.mol2chemfig,a tool for rendering chemical structures from molfile or SMILES format to LATE X code[J].Journal of Cheminformatics,2012,4(1):24.

[4]Dalke A.Parsers for SMILES and SMARTS[J].Chemistry Central Journal,2008,2(1):1.

[5]Bonnici V,Giugno R,Pulvirenti A,et al.A subgraph isomorphism algorithm and its application to biochemical data[J].BMC Bioinformatics,2013,14(7):1-13.

[6]LI Yan,ZHOU Jiaju.Application of VF algorithm in chemical structure retrieval[J].Computer and Applied Chemistry,2002,19(5):575-576(in Chinese).[李琰,周家駒.VF算法在化學結構檢索中的應用[J].計算機與應用化學,2002,19(5):575-576.]

[7]Dallakian P,Haider N.FlaME:Flash molecular editor-a 2D structure input tool for the web[J].Journal of Cheminforma-tics,2011,3(1):6.

[8]LI Chuangye.Network retrieval of compound structure[D].Tianjin:Hebei University of Technology,2007(in Chinese).[李創業.化合物結構的網絡檢索[D].天津:河北工業大學,2007.]

[9]PAN Kai.The design and implementation of the retrieval method of chemical molecular substructure in ChemDataBase database[D].Lanzhou:Lanzhou University,2009(in Chinese).[潘凱.ChemDataBase數據庫中化學分子子結構檢索方法的設計與實現[D].蘭州:蘭州大學,2009.]

[10]LIU Shuwen.Handbook of synthetic perfume technology[M].Beijing:China Light Industry Press,2000(in Chinese).[劉樹文.合成香料技術手冊[M].北京:中國輕工業出版社,2000.]

[11]Makarova K S,Koonin E V.Evolution and classification of CRISPR-Cas systems and Cas protein families[M]//CRISPR-Cas Systems.Springer Berlin Heidelberg,2013:61-91.