研究主題：應用混合式基因演算法於氧端連結糖基化位置具有糖基轉移 酶受質專一性辨別的特徵選取
摘要
生物體中超過50%的蛋白質存在糖基化修飾，糖蛋白參與了眾多重要的生命過程，包括免疫、生殖、病原感染、癌症…等，是非常重要的蛋白質轉譯後修飾之一。現今研究已將糖基化所附加上的醣基做分類，分析其特徵，并使用 AAC+AAPC特徵屬性，進行模擬測試及評估來測試，但特征屬性比較多，分析起來較複雜，因此本研究針對以上問題提出應用混合式基因演算法和類免疫演算法於氧端連結糖基化位置具有糖基轉移酶受質專一性辨別的特徵選取。
本文混合式基因演算法和類免疫演算法的適應函數都引用了LIBSVM自動查找最佳參數來建立模型的方法來取得更高的準確度，採用類似生物學上的複製、交配和突變來改變所挑選的序列。基因演算法還增加了五條隨機產生的母體，增加其多样性和提高其預測的準確度。类免疫演算法相较于基因演算法具有记忆功能，即能保留前一代准确度高的序列，使得收斂的速度比較快又不存在過早收斂的弊端。最後，我們用生物學數據對其進行了檢驗，證明了該方法的可用性。
關鍵字： 特征選取，基因演算法，類免疫演算法，LIBSVM
一、研究背景與動機
根据糖苷链类型，蛋白质糖基化可以分为四类，即以丝氨酸、苏氨酸、羟赖氨酸和羟脯氨酸的羟基为连接点，形成0-糖苷键型。以天冬酰胺的酰胺基、N一末端氨基酸的 α - 氨基以及赖氨酸或精氨酸的ω - 氨基为连接点，形成-N-糖苷键型;以天冬氨酸或谷氨酸的游离羧基为连接点，形成脂糖苷键型以及以半胱氨酸为连接点的糖肽键。氧端連結糖基化(O-linked Glycosylation)是在酶的控制下，蛋白質或脂質的絲胺酸，蘇胺酸，酪胺酸，羟赖胺酸，或羥脯胺酸側鏈的羥基氧或氧原子上附加上糖類的過程，是共轉譯（co-translational）與轉譯後修飾的形式之一。轉譯後修飾和許多生物反應過程息息相關，包括了轉錄的調控、細胞的凋亡和細胞信號的傳遞。生物體中超過50%的蛋白質存在糖基化修飾，糖蛋白參與了眾多重要的生命過程，包括免疫、生殖、病原感染、癌症…等，是非常重要的蛋白質轉譯後修飾之一。現今研究已將糖基化所附加上的醣基做分類，分析其特徵，并使用 AAC+AAPC特徵屬性，進行模擬測試及評估來測試，但特征屬性比較多，分析起來較複雜，浪費資源，因此本研究針對以上問題提出應用混合式基因演算法和類免疫演算法於氧端連結糖基化位置具有糖基轉移酶受質專一性辨別的特徵選取,希望能夠通過混合式的基因演算法進行特征選取，節省時間跟資源。
蛋白质组成结构图
二、数据预处理
2.1 数据来源
氨基酸是生物学上重要的有机化合物，它是由胺（-NH2）和羧酸（-COOH）的官能团组成的，以及一个侧链连到每一个氨基酸。氨基酸是构成蛋白质的基本单位。蛋白质经水解后，即生成20种氨基酸，如甘氨酸（Glycine，縮寫G）、丙氨酸（Alanine，縮寫A）、缬氨酸（Valine，縮寫V）、亮氨酸（Leucine，縮寫L）、异亮氨酸（Isoleucine，縮寫I）、苯丙氨酸（Phenylalanine，縮寫F）、色氨酸（Tryptophan，縮寫W）、酪氨酸（Tyrosine，縮寫Y）、天冬氨酸（Aspartic acid,，縮寫D）、组氨酸（Histidine，縮寫F）、天冬酰胺（Asparagine，縮寫N）、谷氨酸（Glutamic acid，縮寫E）、赖氨酸（Lysine，縮寫K）、谷氨酰胺（Glutamine，縮寫Q）、甲硫氨酸（Methionine，縮寫M）、精氨酸（Arginine，縮寫R）、丝氨酸（Serine，縮寫S）、苏氨酸（Threonine，縮寫T）、半胱氨酸（Cysteine，縮寫C）、脯氨酸（Proline，縮寫P）等，本实验還添加一個X,代表任意氨基酸殘基。
本实验採用了AAC+AAPC矩陣方法來轉換序列。AAC matrix就是統計一個氨基酸在序列中出現的次數，因為總共有21個氨基酸，也就有21個值，每個值就是相對應的氨基酸出現的次數除以總氨基酸數21，就得到了21個特征向量，如圖所示。
2.2 分类方法——Libsvm
支持向量机（英语：Support Vector Machine，常简称为SVM，又名支持向量网络）是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。LIBSVM是台湾大学林智仁教授等开发设计的一个简单、易于使用和快速有效的SVM模式识别与回归的软件包。该软件对SVM所涉及的参数调节相对比较少，提供了很多的默认参数，利用这些默认参数可以解决很多问题，并提供了交互检验(Cross Validation)的功能。该软件可以解决C-SVM、ν-SVM、ε-SVR和ν-SVR等问题，包括基于一对一算法的多类模式识别问题。
LIBSVM使用的使用的训练数据和检验数据文件格式如下：
<label> <index1>:<value1> <index2>:<value2> ...
其中<label> 是训练数据集的目标值，对于分类，它是标识某类的整数（支持多个类）；对于回归，是任意实数。 <index> 是以1开始的整数，可以是不连续的；<value>为实数，也就是我们常说的自变量。检验数据文件中的label只用于计算准确度或误差，如果它是未知的，只需用一个数填写这一栏，也可以空着不填。
三、研究方法
3.1 基因演算法
基因演算法(Genetic Algorithms)主要是John Holland 於1975年所提出，其根據來源則是自然界遺傳法則，即達爾文提出的「物競天擇，適者生存」，解釋了自然界演化的現象，物種在不斷的變化或惡劣的環境考驗中，彼此競爭下，為了求生存及適應環境，不斷的繁殖進化將優良的基因延續，產生生存力和適應力更強的下一代。Genetic Algorithms常被用來求最佳化，經由複製（Reproduction）、交配（Crossover）與突變(Mutation)，周而復始地進行一代又一代演化，選擇適合生存的下一代。在基因演算法中，突變是一重要機制，可用來避免掉入區域極值中，順利找到函數極值。
基因演算法流程图如图所示，以下針對流程步驟簡單說明：
1、產生初始族群母體
將未處理過的數據劃分成五個文檔，隨機挑選出四個文檔作為初始文檔，然後產生十條根據一定的百分比隨機產生一些數，挑選出隨機數為1對應特徵值的數據作為初始族群母體，五條母體用于傳統的基因演算法，五條母體隨機產生序列增加多樣性；
2、適應函數值
將初始族群母體數據轉換成libsvm方法適用的數據類型，然後調用libsvm方法，找出最佳參數，建立好的模型進行預測，然後將預測的結果與原始數據進行比較得出TP、TN、NP、NT這四個數值，再根據每個數值所分配到的權重計算出總和得適應函數值；
3、終止條件
當一個百分數連續四代的函數適應值都差不多之後就進入下一個百分數，否則就進行選擇、交配、突變和隨機產生五條母體等操作。當穩定后的函數適應值低於某一特定值時，則停止；否則進入下一個百分數，即減少特徵值，穩定之後再繼續判斷。
AAC數據選取
AAPC數據選取
基因演算法流程圖
基因演算法的特性及優缺點
基因演算法的特性：
1.多點搜尋
加入了五條隨機產生母體還有複製、交配、突變等動作，避免落入區域最佳解的陷阱。
2.概率規則
基因演算法使用概率的方式來引導搜尋方向，並非既定規則，符合各種類型的最佳化問題。
優點：
1. 基因演算法以隨機搜尋的法則，因此可在求解空間上任意的跳動而不受限制，有較好的機會求得全域最佳解。
2.使用libsvm自動搜索最佳參數，提高了母體的準確度。
缺點：
1.在有限的搜尋空間內，基因演算法無法保證每次執行都能收斂到相同解。
2.只以準確度作為適應函數值容易導致其他參數較低。
3.基因演算法的求解時間隨染色體資串位元數的增加成指數增加。
3.2 類免疫演算法
類免演算法是利用適應性免疫反應的特性所衍生出來的，其是效仿生物免疫系統中抗體對抗外來病原體的機制，所發展出來搜尋最佳解的一種演算法。類免疫演算法是以免疫演算法加入人工智慧技術，使得求解過程能更快速收斂。免疫網路理論最早是峹在1974 年岩由Jerne所提出，意指在真實的免疫系統中，當生物遇到外界病源物質入侵，所引起生物保護性能力之病源物質在體內被稱為抗 原（Antigen, Ag），而免疫反應是利用體內產生的抗體（Antibody, Ab）來與抗原結合達到抑制抗原的動作。藉由抗體抑制抗原此機制，免疫系統提供一個良好的最佳化方法，便以此免疫反應中抗體辨識抗原的專一性而將抗原比作為目標函數，抗體視為問題之可行解，針對抗原來搜尋可與只相結合的抗體亦即尋找問題之解答。
在類免疫演算法中，是以抗體對抗原進行辨識與抑制，除了考慮抗體與抗原之間的匹配性，對於整個系統也考慮了抗體與抗體，彼此間的關聯，此外也結合了輔助與抑制型的T-cell，以及記憶型細胞之共演化的概念，在融合兩個演算法的特點，進而衍生出本研究之強化型混合免疫基因演算法(EHIGA)。
EHIGA 是仿效生物系統的演化機制，以運算元的概念與方式呈現出來，主要的演化策略除了以B-Cell 中的突變與片段交換機制，來產生更多樣化的抗體，而在T-Cell 則是根據基因所蘊含之資訊來產生輔助性抗體，並且加入產生人造抗體，以加強其收斂性，期望能結合此兩大機制使演化能兼具廣度及深度搜尋。親和力的依據則是計算每條抗體與抗原的適應值，期望將尋解的範圍定位在真正問題解的抗原附近，而選擇的機制則是篩選抗體，先保留適應值較好的抗體，另外也產生與保留差壓較大的抗體，再對抗體進行基因重組突變與片段交換。
類免疫演算法的示意圖如下圖所示：
EHIGA流程圖
以下針對類免疫流程圖的重要步驟作簡單說明：
1、產生初始抗體
與基因演算法類似，即先將未處理過的原始數據劃分成五個文檔，抽出四個文檔作為訓練集，產生五條根據隨機產生數為1所對應特徵值的數據作為母體。
2、計算抗體適應值
將初始族群母體數據轉換成libsvm方法適用的數據類型，然後調用libsvm方法，找出最佳參數，建立好的模型進行預測，然後將預測的結果與原始數據進行比較得出TP、TN、NP、NT這四個數值，再根據每個數值所分配到的權重計算出總和得適應函數值；
3、記憶型細胞
EHIGA演算法流程會有兩部份的抗體合稱為記憶型細胞，此是參考了類免疫演算法當中記憶的特性，在過程中會保留一定比例較好的抗體，在測試點選取的
問題上所代表的就是適應值最好，也就是先考量涵蓋率最高者，另外是每隔n個世代就會將最好抗體即菁英抗體全部保留，再保存其三分之二的抗體，三分之一隨機產生，其目的就是要記憶與保留適應值較好的抗體，其中績效較好的片段，以提昇抗體的整體效能與品質。
產生差異較大的抗體是將其序列與菁英抗體做對比，不同序列超過三分之二的抗體才會被保留下來，其目的就是為了增加問題解的多樣性，避免局限在部分區域。
4、片段交換與重組突變
EHIGA演算法對抗體進行片段交換，其方式就如同基因演算中交配的過程，
選擇2條抗體做部份基因片段的交換，本論文所使用的交配方法是單點交配，以隨機的方式在基因串列中挑選一個交配點，將交配點之後的基因進行互換的動作，目的是希望將好的抗體彼此互換有用的情報，如此便可增進好的抗體的本質與數量，另外對抗體做重組突變所使用的突變方法是單點突變，基因演算法中突變的原理也是用此方式，希望藉由一定比例的突變，增加抗體種類的多樣性與廣度，用以對抗與試圖找出未知抗原的最佳解。
5、新抗體族群
從T-Cell、B-Cell 及記憶細胞所產生之抗體，其內容包括選擇部份較好的抗體與產生差異較大的抗體，以及經過片段交換與重組突變的抗體，三個部份彙總之後，依照涵蓋率的大小排序，相同的涵蓋率則再以價格的高低做排序，價格低的基因串列名次較高，依此原則篩選出下一世代演化的母體族群。
6、B細胞
B細胞是在骨髓內發育成熟的細胞，B細胞受抗原刺激后，可產生漿細胞，而漿細胞會產生抗體來擊退抗原。B細胞具有能與抗原結合的接受器，會在骨髓中必須經歷許多次的基因重組階段，其目的是為了增加將來產生抗體時的多樣性，以產生各種不同的抗體。抗體有出色的記憶力和識別力，當同樣的敵人再次出現時，由於這些抗體與原先的受器分子有相同的結構，因此可與那些活化B細胞的抗原結合。
7、T細胞
T細胞是在胸腺中成熟的細胞，按功能可分為輔助性T細胞(T Helper cell,TH)、抑制性T細胞(T Suppressor cell,TS)和毒殺性T細胞(T Cytotoxic cell)，其中TH、TS主要起調節作用，也稱為調節性T細胞，TH能夠激活B細胞，幫助其克隆繁殖，而ＴＳ細胞的作用則正好相反。本研究利用簡單基因結構探勘的概念，統計並產生菁英抗體來保留抗原中較好的基因片段，即每隔n世代保留最佳適應值即菁英解的全部序列，并保留其三分之二的序列。
8、終止條件
經過重組突變等操作之後，若連續四代的最佳適應值都差不多就進入下一個百分數即產生１的概率將變低，採用的特徵值將減少，否則就繼續重組突變等操作。當穩定后的最佳適應值小於某一特定值則停止，否則百分數將不斷增加即特徵值將不斷減少。
免疫演算法的特性及優點
特性：
1、識別抗原的不完全匹配性
抗體識別抗原以結合的過程，不一定要二者完全符合，只要兩者間之親和力達到某一門檻值即可。
2、多樣性識別能力
單一免疫細胞可以識別多種不同的抗原的能力，抗體隨著抗原的不同隨之改變與抗原結合的方式，進一步消滅抗原。
3、學習與記憶
能夠學習與記憶病原體的結構，也就是目前較符合最佳化的解，并以此解之狀態再由求解空間搜尋。
4、細胞突變
亦即體細胞成熟，此機制可使得免疫系統辨識多種抗原，且可對抗不同的抗原，進而提高抗體族群的雜異度，也避免造 成過早收斂之現象。
優點：
1、抗體在辨識抗原時，不僅考慮到抗體與抗原的匹配性，同時也考慮到系統中抗體彼此間的互助關係，因此免疫有較佳 的辨識力。
2、同時搜尋多個最佳點，而傳統數學方法通常一次只搜尋一個解，最後只求得一個解。
3、具有免疫記憶庫，并對於處理自組記憶有較長的時效性，指再次遇到相同的抗原，可以快速反應進而抑制。
缺點：
1、收斂速度較為緩慢。
2、由於類免疫演算法求解特性為透過突變機制尋求足以對抗抗原之抗體，因此求解品質變異較大。
3.3 類免疫演算法與基因演算法的異同點
基因演算法（GA）與類免疫演算法（AIS）皆是模仿生物系統的機制所衍生出來的演算法，兩者利用生物的學習與運作量化成咨詢系統的模式進行求解，在最佳化問題中應用非常廣泛。然而，雖然兩種演算法很相像，但仍然有許多不同的地方，以下表匯整了相關文獻比較兩者只異同點。
四、实验结果
此次實驗中，主要目的就是希望能夠找出有用的特徵值，使得不需要全部的特徵值也能達到較高的準確度。所以，我們用libsvm方法自動挑選最佳參數來建立模型并達到較高的準確度，除此之外我們將適應函數定義為TP、TN、FP、FN不同權重之和，并找出較佳的權重比例，得到了較佳的效果。
參考文獻
1、百度百科.LIBSVM[EB/OL].<http://baike.baidu.com/item/LIBSVM>.2016
2、Edison.x.[GA] 基因演算法(Genetic Algorithm, GA) - Introduction and C code[EB/OL].2012
3、黃冠傑.基因演算法求函數極值[R]. 2019
4、羅慧文.以類免疫算法求解流程型排程問題[D].台灣：元智大學.2010
5、維基百科.氨基酸[EB/OL].
https://zh.wikipedia.org/wiki/%E6%B0%A8%E5%9F%BA%E9%85%B8.2016
6、https://www.neb.com/tools-and-resources/feature-articles/the-structure-function-and-importance-of- carbohydrates
