Selected Article

Title

遺傳演算法/禁忌搜尋法應用於計算生物學之多重序列排比

[[alternative]]A GA/Tabu Search for Multiple Sequence Alignment in Computational Biology

Description

[[abstract]]多重序列排比(MSA, Multiple Sequence Alignment )在生物資訊學中是一個很重要也具有挑戰性的問題,我們能透過多重序列排比了解序列之間結構上的差異及隱含的資訊,但是它的問題複雜度卻相當高,粗略地說,比較兩個長度皆為n的序列所需的時間是和n的平方成正比的;而比較k個長度皆為n的序列所需的時間則和n的k次方成正比。本論文將應用基因演算法結合禁忌搜尋法,提供另一個解決問題的方法。論文實驗將利用PAM 250得分矩陣及16組蛋白質序列(Protein Sequence)進行,並和多重序列排比軟體ClustalW做比較,由數據中發現本論文所提出之方法能得到較好的結果。

[[abstract]]Multiple Sequence Alignment(MSA) is a very important issue, and also a big challenge in computational biology. We can know the structural differences and some hidden information between sequences by means of MSA. Multiple Sequence Alignment(MSA) is a very complicated problem, roughly speaking, the time for comparing 2 lengths, which are both as the sequence of n, is a direct proportion/ ratio to the square of n; nevertheless the time for comparing k lengths, which are all the sequence of n, will get a direct proportion/ratio of k to the power. In this paper, we proposed a hybrid method of Genetic Algorithm and Tabu Search. We use PAM 250 scoring matrix and 16 groups of protein sequences to execute the experiments and compare with the Multiple Sequence Alignment Sofrware – ClustalW. Experimental results show that, in our method,we can get the batter solution.