Browsing by Author "LU CHIN LUNG"

Now showing 1 - 8 of 8

偵測程序性核糖體移碼的演算法研究及其軟體工具的發展
(2006)
盧錦隆
;
LU CHIN LUNG
;
國立交通大學生物科技學系(所)
程序性核糖體的移碼(Programmed Ribosomal Frameshifting)是一種基因重新編碼(Recoding)的機制，其可造成轉譯(Translational)的核糖體(Ribosome)在一個特定的位置上從一個讀碼框(Reading Frame)更換到另一個讀碼框，使得蛋白質的轉譯能夠在新的讀碼框繼續下去，最後產生一個由前後兩個讀碼框共同編碼的融合蛋白質(Fusion Protein)。到目前為止，程序性核糖體移碼已在許多的致病性病毒(包括嚴重急性呼吸道症候群的SARS冠狀病毒)及轉座因子(Transposable Elements)上被發現，甚至也出現在少數的原核及真核生物上。在目前被發現的病毒上，即便對其程序性核糖體移碼的效率做些小小的改變，皆能有效地抑制該病毒的繁殖，這代表程序性核糖體的移碼可做為抗病毒療法(Antiviral Therapeutics)的可能標的物(Target)。因此，設計出一個有效且準確的生物資訊演算法及軟體工具，來快速正確地找到在核糖核酸序列上會發生程序性核糖體移碼的位置便是一個非常重要的事情。目前最常見到的程序性核糖體移碼便是所謂的『倒退一個核.酸的』程序性核糖體移碼(Programmed -1 Ribosomal Frameshifting，簡稱-1PRF)，因為它的發生會迫使轉譯中的核糖體倒退一個核.酸之後再繼續轉譯下去。目前已有許多的計算方法譬如說圖樣辨認 (Pattern Recognition)、統計分析(Statistical Analysis)以及機器學習(Machine Learning)等方法已被提出，可以用來識別在核糖核酸序列上的程序性核糖體移碼位置。然而，大都數的方法常常找出太多不是真正的程序性核糖體移碼【即所謂的False Positives】，甚至有些無法找到真正的程序性核糖體移碼【即所謂的True Positives】。特別值得一提的是這些方法皆有一個共同的缺點：即他們用來預測做為-1 PRF刺激物(Stimulator)的RNA結構【一般而言應該是所謂的H-型假結(H-type Pseudoknots)】太過簡單，以致於他們所預測出來的RNA結構【常為簡單的Stem-Loops】不是那麼的隱定可以有效地成為-1 PRF的刺激物。最近，我們成功地發展出一套啟髮式(Heuristic)的方法能夠有效且準確地預測出在給定的一條RNA序列上的H-型假結【Huang, C.-H., Lu, C. L. and Chiu, H.-T. Bioinformatics, Vol. 21, 2005, pp. 3501-3508】。我們相信我們發展的這個方法是有助於-1 PRF刺激物的識別，故我們認為我們有很大的機會可以大大地改進目前方法的敏感度(Sensitivity)及專一性(Specificity)。因此，在這個計劃提案中，我們打算進一步的適度修改我們所發展出來預測H-型假結方法，並以它為核心去設計出有效且準確的方法來預測出RNA序列上-1 PRF的位置。除此之外，我們也會根據我們設計出來的演算法去實做(Implement)出一個網路伺服器(Web Server)，以便能夠開放給一般使用者去進行線上的-1 PRF分析。為了要能夠展現我們系統的適用性及準確性，我們也打算利用一些事先已給知道具有-1 PRF的RNA序列(包含SARS冠狀病毒序列)來測試我們的系統，並將這個測試實驗結果跟目前現有的程式做個比較。
基因體重組問題---理論與應用
(2007)
盧錦隆
;
LU CHIN LUNG
;
國立交通大學生物科技學系(所)
隨著大量基因體序列的出現，基因體重組的研究在計算生物及生物資訊的領域上愈來愈受到重視。研究基因體重組的主要目的是藉由比較基因體上的基因次序以衡量出兩個物種之間的演化差異。目前有許多會改變基因次序的重組已被提出，如翻轉(Reversals)、移位(Transpositions)、區段互換(Block-Interchange)、分裂(Fissions)、融合(Fusions)、易位(Translocations)等等。給定二個基因體上基因次序的排列，『基因重組問題』是要去計算出一條最短的重組序列可以把其中一組基因體上的基因次序轉換成另外一組基因體的基因次序，其中所需用到的最少重組個數就被稱為『重組距離』。先前有關這個問題的大部份研究與成果都把焦點放在如何利用圖論的(graph-based)方法與分析設計出有效率的(近似)演算法。然而，大部份這些研究所設計出來的演算法與所需的資料結構都太過複雜故不易寫成程式。過去這二、三年來，我們成功地利用代數排列群(Permutation Groups)的特性與方法設計出較簡單且有效率的演算法解決區段互換的基因重組問題及融合+分裂+區段互換的基因重組問題。因此在這個計劃提案中，我們將繼續去研究如何把這個代數方法應用到其它的基因重組問題如翻轉、移位(可被視為區段互換的特例)、易位(可被視為融合與分裂的延伸)以及他們之間可能的組合。值得注意的是上述基因重組問題的研究皆需要一個前提，即參與比較的基因得是基因體之間相同且唯一(不重複)的基因(即1-1的直系同源基因；1-1 Orthologs)才行；然而一個基因在物種的基因體上可能會出現好幾份(即共生同源基因；Paralogs)。在這個情況之下，生物學家為了要能夠繼續使用現有且針對1-1直系同源基因的基因體所設計出來的演算法，他們經常被逼不得不刪除掉在基因體上一些重複的共生同源基因。這樣妥協對於小型基因體(如病毒和粒腺體)的演化樹建構還能行得通，但不可必免地對於一些較複雜的基因體(如原核與真核生物)其正確性便會因為資料的刪除而所有失真。Sankoff (1999)最先探討這個問題並定義出一個稱之為『廣義的基因重組問題』，其目的是要去刪除每一個基因家族中重複的基因直到只剩一個，並且使得經過刪除後剩餘的二個基因體之間的重組距離為最小。目前這部份的研究成果還很少，除了已經知這個問題在考量斷點(Breakpoint)距離或翻轉距離最佳化的時候是一個NP-hard的問題。因此在本計劃提案中我們也要去研究與探討要最佳化移位、區段互換或是易位距離的情況下，廣義的基因重組問題是否仍是一個NP-hard的問題？或是可在多項式時間內被解決的問題？最後，我們也將對本計劃未來執行中所設計出來的演算法給予程式化，並整合我們之前已發展出來的程式(如ROBIN, SPRING和FFBI)成為一個網路伺服器以協助生物學家能依據基因重組的分析去建構出一些物種之間的演化關係。
基因體重組的研究及其軟體工具的發展和應用
(2005)
盧錦隆
;
LU CHIN LUNG
;
國立交通大學生物科技學系(所)
隨著各種基因體序列(如DNA、RNA及蛋白質序列)的普及，基因體重組(Genome Rearrangement)的研究在計算生物(Computational Biology)及生物資訊(Bioinformatics)的領域上漸漸受到眾人的矚目。基因體重組研究的主要目的是藉由大型基因體的比較去衡量兩種生物體之間在演化上的差異。其中最為可行的大型基因體比較方法之一是比較兩種不同生物體之間其共有基因在基因體上次序的差異。不像插入(Insertions)、刪除(Deletions)、及取代(Substitutions)這些傳統的點突變，各種大型基因體突變(Large-Scale Mutations)例如翻轉(Reversals)、移位(Transpositions)、區塊互換(Block-Interchanges)、分裂(Fissions)、融合(Fusions)及易位(Translocations)等等已被提出並藉此以比較二個相關基因體之間共有基因次序的差異以決定出他們在演化上的矩離。通常，基因體重組的研究都能夠被描述成一個找出最少的大型基因體突變來把一個基因體轉變成另一個基因體的組合數學問題。因此，這個計劃的主要目的是要去研究並解決在不同的大型基因體突變考量之下各種基因體重組的問題，特別是移位、區塊互換、翻轉式移位(Inverted Transpositions)和翻轉式區塊互換(Inverted Block-Interchange)等這幾個大型基因突變。在計算理論方面，我們將嘗試著利用代數中群論(Permutation Groups)的性質和在區塊互換考量之下我們所發展出來解決基因體重組問題的一些演算法技巧，去設計出有效率的求最佳解的演算法或是簡單的求近似解的演算法來解決分別在移位、翻轉式移位和翻轉式區塊互換考量之下的基因體重組問題。在實際應用方面，我們將對本計劃所設計出來的演算法去實做出他們的程式，並整合一些現有的程式去建構出一個基因體重組有關的網頁伺服器，來幫忙生物學家在各種大型基因體突變考量之下，去比較一些生物體的基因次序資料之間的差異，進而衡量出他們之間的演化差異。為了要讓這個系統也能處理序列資料，我們將進一步提升系統的功能使之能夠自動化地偵測出所有輸入序列彼此之間所共有的同源或保守的區域。除此之外，這個系統也會整合NJ (Neighbor Joining) 和UPGMA (Un-weighted Pair-Group Method using Arithmetic mean) 的程式使之也能夠利用系統所計算出來任兩生物體之間的矩離重建出他們的演化樹。
建置新一代高通量定序分析平台---從定序、功能、到系統生物網路---利用次世代定序資料進行基因體重組的研究與結構變異的偵測
(2011)
盧錦隆
;
LU CHIN LUNG
;
國立交通大學生物科技學系（所）
次世代定序(NGS)技術使得基因體的定序愈來愈快也愈來愈便宜，可以預期不久的將來會有許多物種的基因體被NGS 技術給定序出來。然而目前NGS 技術所定序出來的基因體大都只是由一些前後次序未知的contigs/scaffolds 所組成的草圖。雖然這些基因體草體可能就已足夠讓科學家進行許多比較基因體的分析，但卻不能直接被拿來進行基因體重組的研究，因為目前被設計出來的基因體重組演算法需要完整的基因體資料，基因體裡的每一個染色體皆用基因或標記的次序來表示，才能夠去計算出二個基因體之間的重組距離。因此如何設計出有效率的基因體重組演算法把前後次序未知的contigs/scaffolds 給組合起來並正確地計算出組合基因體之間的重組距離，以及如何利用這些重組距離去建構出不同物種之間的演化關係將是本子計劃的主要研究課題之一。除此之外，本子計劃也將進一步去研究如何偵測出發生在這些組合基因體上大規模的結構變異，這些結構變異(包含DNA 片斷的插入、刪除、翻轉、移位、區段互換、易位、融合、分裂等)常與癌症的發生息息相關，因此找出癌症基因體上的結構變異將有助於人類癌症與其它疾病的診斷與治療，同時也可幫助我們了解基因體在生命演化的過程中是如何成形的。
有效率的位元平行演算法以解決近似字串比對問題
(2011)
盧錦隆
;
LU CHIN LUNG
;
國立交通大學生物科技學系（所）
在傳統的字串演算法裡，近似字串比對是主要的問題之一，因為它可應用在許多不同的地方包括文章搜尋、字串辨識與計算生物等等。給予一個全文字串T t1t2tn  與一個樣本字串m P p1 p2p  ，近似字串比對問題的目的是要去尋找全文字串裡所有的位置使得結束在這些位置的子字串都與樣本字串之間的編輯距離小於或等於一個事先給定的錯誤邊界值k，或者同等於對全文字串裡的每一個位置 i，去找出T(1,i)的字尾使得這個字尾與樣本字串之間的編輯距離小於或等於k，其中n T t1t2t  (即T 中長度為i 的字首)。傳統解決這個近似字串比對問題的方法就是利用一個動態規劃演算法去填寫一個大小為(m+1)×(n+1)的矩陣，因此它的時間複雜度為O(mn)。到目前為止，這個動態規劃演算法的執行效能已經被利用許多不同的方法加以改進了許多次，其中之一便是所謂的位元平行演算法，它是利用硬體上位元運算的平行特行來加速執行效能。如果同時允許插入、刪除與替換這三種編輯指令的話，那麼Myers 在1999 年所提出的位元平行演算法是目前最好的之一，時間複雜度為O(mn/w)，其中w 為電腦字的長度。然而，在實際的應用上，位元平行演算法經常得飽受一個嚴重的問題，那就是樣本字串的長度得受限於電腦字的長度。如何讓位元平行演算法能以一種比較有效率的方法來處理長的樣本字串目前仍是一個挑戰。因此在本計劃中，我們將去研究如何利用邏輯向量與邏輯運算來設計出一個比較有效率的位元平行演算法可以打破樣本字串的長度限制並且能夠更有效率地來解決近似字串比對問題。
開發生物資訊新工具去探索RNA病毒序列、結構、功能與演化---以流感病毒與腸病毒為應用模型---含有假結的RNA二級結構預測與其在偵測程序性核糖體移碼基因的應用
(2010)
盧錦隆
;
LU CHIN LUNG
;
國立交通大學生物科技學系（所）
幾乎在所有自然存在的RNA結構中皆可發現所謂的假結(Pseudoknot)，其在各種的生物反應中如RNA的複製、轉錄與轉譯等等扮演著非常重要的角色。例如他們可以擔任程序性核糖體移碼(Programmed Ribosomal Frameshifting)的刺激物。所謂的程序性核糖體移碼乃是一種重新編碼(Recoding)的機制，而且經常在很多的RNA病毒(如SARS冠狀病毒)上被發現。病毒藉由這個機制，可讓正在進行轉譯的核糖體在某一個特定的位置上從原來的讀碼框(Open Reading Frame)切換到新的讀碼框(如-1或+1讀碼框，其中切換到-1讀碼框者佔大多數)，結果產生另一個新的蛋白質，其不同於原來不發生移碼時所產生的蛋白質。據文獻的報導對於利用此機制的病毒，即便很小地改變其移碼效率就可以抑制其繁殖，這意味著程序性核糖體移碼位置可充當抗病毒藥劑的標的。目前為止，被發現的RNA假結大多數是所謂的H型結構，基本上它是一個髮夾(Hairpin)的結構，其中在髮夾迴圈(Hairpin Loop)的核苷酸會和髮夾外面的核苷酸配對並形成一個靠近或非常靠近髮夾的螺旋主幹(Helical Stem)。事實上，較複雜的H型假結也曾被發現，比如說在SARS冠狀病毒上擔任程序性核糖體移碼刺激物的假結就比平常的H型假結多出一個主幹出來。因此，預測這些H型甚至更複雜的假結結構將有助於我們對RNA結構與其功能的了解。在一般標準的熱動力模型(Thermodynamic Model)上，不含假結的最小自由能量(Minimum Free Energy)的RNA二級結構是可以在多項式時間(Polynomial Time)內被計算出來。然而，要去計算含有假結的最小自由能量的RNA二級結構便變成了一件非常困難的事情，因為它已被證明出是件NP-hard的問題。目前已有許多的多項式時間的演算法被設計出來可以用來計算出含有特定型態的假結(如H型假結)的最小自由能量的RNA二級結構。然而，這些演算法的時間與空間(即記憶體)複雜度仍非常的高，故尚不能實際地被拿來處理較長甚至大型的RNA序列。除此之外，這些演算法也不見得能夠偵測出在一條長的RNA序列中所含的H型假結。過去，我們已經提出一個啟發式(Heuristic)的方法可以改進這些演算法去預測H型的假結，同時也把它應用到-1和+1型程序性核糖體移碼的偵測。然而，這個啟發式方法仍有很多可以再被改進與增強的地方，比如說降低其執行時間與所需記憶體的複雜度、增強使其能處理大型序列的能力、改進其預測的準確度、增強使其能夠去預測較複雜的RNA假結結構與偵測其它型態的程序性核糖體移碼(如-2與+2型的程序性核糖體移碼)。在這個子計劃中，我們主要的目的是利用比較基因體學、結構生物資訊學與功能生物資訊學的方法去發展出新的演算法與啟發式方法來進行上述的改良與增強，同時也將去發展出含有假結的RNA二級結構資料庫與程序性核糖體移碼的資料庫。因此，為了完成這些目標我們需要和其他的子計劃成員一起合作，因為他們能夠提供給我們一些在他們研究領域上的專業知識與技術，以及一些在他們子計劃中預期能夠發展出來的相關程式。同時，我們子計劃發展出來的程式與資料庫也能夠幫助其他子計劃成員去研究RNA病毒，例如流行感冒病毒與腸病毒等，並進一步地去探討這些RNA病毒的序列、結構、功能與演化的關係。
開發生物資訊新工具去探索RNA病毒序列、結構、功能與演化---以流感病毒與腸病毒為應用模型---含有假結的RNA二級結構預測與其在偵測程序性核糖體移碼基因的應用
(2008)
盧錦隆
;
LU CHIN LUNG
;
國立交通大學生物科技學系(所)
幾乎在所有自然存在的RNA結構中皆可發現所謂的假結(Pseudoknot)，其在各種的生物反應中如RNA的複製、轉錄與轉譯等等扮演著非常重要的角色。例如他們可以擔任程序性核糖體移碼(Programmed Ribosomal Frameshifting)的刺激物。所謂的程序性核糖體移碼乃是一種重新編碼(Recoding)的機制，而且經常在很多的RNA病毒(如SARS冠狀病毒)上被發現。病毒藉由這個機制，可讓正在進行轉譯的核糖體在某一個特定的位置上從原來的讀碼框(Open Reading Frame)切換到新的讀碼框(如-1或+1讀碼框，其中切換到-1讀碼框者佔大多數)，結果產生另一個新的蛋白質，其不同於原來不發生移碼時所產生的蛋白質。據文獻的報導對於利用此機制的病毒，即便很小地改變其移碼效率就可以抑制其繁殖，這意味著程序性核糖體移碼位置可充當抗病毒藥劑的標的。目前為止，被發現的RNA假結大多數是所謂的H型結構，基本上它是一個髮夾(Hairpin)的結構，其中在髮夾迴圈(Hairpin Loop)的核苷酸會和髮夾外面的核苷酸配對並形成一個靠近或非常靠近髮夾的螺旋主幹(Helical Stem)。事實上，較複雜的H型假結也曾被發現，比如說在SARS冠狀病毒上擔任程序性核糖體移碼刺激物的假結就比平常的H型假結多出一個主幹出來。因此，預測這些H型甚至更複雜的假結結構將有助於我們對RNA結構與其功能的了解。在一般標準的熱動力模型(Thermodynamic Model)上，不含假結的最小自由能量(Minimum Free Energy)的RNA二級結構是可以在多項式時間(Polynomial Time)內被計算出來。然而，要去計算含有假結的最小自由能量的RNA二級結構便變成了一件非常困難的事情，因為它已被證明出是件NP-hard的問題。目前已有許多的多項式時間的演算法被設計出來可以用來計算出含有特定型態的假結(如H型假結)的最小自由能量的RNA二級結構。然而，這些演算法的時間與空間(即記憶體)複雜度仍非常的高，故尚不能實際地被拿來處理較長甚至大型的RNA序列。除此之外，這些演算法也不見得能夠偵測出在一條長的RNA序列中所含的H型假結。過去，我們已經提出一個啟發式(Heuristic)的方法可以改進這些演算法去預測H型的假結，同時也把它應用到-1和+1型程序性核糖體移碼的偵測。然而，這個啟發式方法仍有很多可以再被改進與增強的地方，比如說降低其執行時間與所需記憶體的複雜度、增強使其能處理大型序列的能力、改進其預測的準確度、增強使其能夠去預測較複雜的RNA假結結構與偵測其它型態的程序性核糖體移碼(如-2與+2型的程序性核糖體移碼)。在這個子計劃中，我們主要的目的是利用比較基因體學、結構生物資訊學與功能生物資訊學的方法去發展出新的演算法與啟發式方法來進行上述的改良與增強，同時也將去發展出含有假結的RNA二級結構資料庫與程序性核糖體移碼的資料庫。因此，為了完成這些目標我們需要和其他的子計劃成員一起合作，因為他們能夠提供給我們一些在他們研究領域上的專業知識與技術，以及一些在他們子計劃中預期能夠發展出來的相關程式。同時，我們子計劃發展出來的程式與資料庫也能夠幫助其他子計劃成員去研究RNA病毒，例如流行感冒病毒與腸病毒等，並進一步地去探討這些RNA病毒的序列、結構、功能與演化的關係。
開發生物資訊新工具去探索RNA病毒序列、結構、功能與演化---以流感病毒與腸病毒為應用模型-含有假結的RNA二級結構預測與其在偵測程序性核糖體移碼基因的應用
(2009)
盧錦隆
;
LU CHIN LUNG
;
國立交通大學生物科技學系(所)
幾乎在所有自然存在的RNA結構中皆可發現所謂的假結(Pseudoknot)，其在各種的生物反應中如RNA的複製、轉錄與轉譯等等扮演著非常重要的角色。例如他們可以擔任程序性核糖體移碼(Programmed Ribosomal Frameshifting)的刺激物。所謂的程序性核糖體移碼乃是一種重新編碼(Recoding)的機制，而且經常在很多的RNA病毒(如SARS冠狀病毒)上被發現。病毒藉由這個機制，可讓正在進行轉譯的核糖體在某一個特定的位置上從原來的讀碼框(Open Reading Frame)切換到新的讀碼框(如-1或+1讀碼框，其中切換到-1讀碼框者佔大多數)，結果產生另一個新的蛋白質，其不同於原來不發生移碼時所產生的蛋白質。據文獻的報導對於利用此機制的病毒，即便很小地改變其移碼效率就可以抑制其繁殖，這意味著程序性核糖體移碼位置可充當抗病毒藥劑的標的。目前為止，被發現的RNA假結大多數是所謂的H型結構，基本上它是一個髮夾(Hairpin)的結構，其中在髮夾迴圈(Hairpin Loop)的核苷酸會和髮夾外面的核苷酸配對並形成一個靠近或非常靠近髮夾的螺旋主幹(Helical Stem)。事實上，較複雜的H型假結也曾被發現，比如說在SARS冠狀病毒上擔任程序性核糖體移碼刺激物的假結就比平常的H型假結多出一個主幹出來。因此，預測這些H型甚至更複雜的假結結構將有助於我們對RNA結構與其功能的了解。在一般標準的熱動力模型(Thermodynamic Model)上，不含假結的最小自由能量(Minimum Free Energy)的RNA二級結構是可以在多項式時間(Polynomial Time)內被計算出來。然而，要去計算含有假結的最小自由能量的RNA二級結構便變成了一件非常困難的事情，因為它已被證明出是件NP-hard的問題。目前已有許多的多項式時間的演算法被設計出來可以用來計算出含有特定型態的假結(如H型假結)的最小自由能量的RNA二級結構。然而，這些演算法的時間與空間(即記憶體)複雜度仍非常的高，故尚不能實際地被拿來處理較長甚至大型的RNA序列。除此之外，這些演算法也不見得能夠偵測出在一條長的RNA序列中所含的H型假結。過去，我們已經提出一個啟發式(Heuristic)的方法可以改進這些演算法去預測H型的假結，同時也把它應用到-1和+1型程序性核糖體移碼的偵測。然而，這個啟發式方法仍有很多可以再被改進與增強的地方，比如說降低其執行時間與所需記憶體的複雜度、增強使其能處理大型序列的能力、改進其預測的準確度、增強使其能夠去預測較複雜的RNA假結結構與偵測其它型態的程序性核糖體移碼(如-2與+2型的程序性核糖體移碼)。在這個子計劃中，我們主要的目的是利用比較基因體學、結構生物資訊學與功能生物資訊學的方法去發展出新的演算法與啟發式方法來進行上述的改良與增強，同時也將去發展出含有假結的RNA二級結構資料庫與程序性核糖體移碼的資料庫。因此，為了完成這些目標我們需要和其他的子計劃成員一起合作，因為他們能夠提供給我們一些在他們研究領域上的專業知識與技術，以及一些在他們子計劃中預期能夠發展出來的相關程式。同時，我們子計劃發展出來的程式與資料庫也能夠幫助其他子計劃成員去研究RNA病毒，例如流行感冒病毒與腸病毒等，並進一步地去探討這些RNA病毒的序列、結構、功能與演化的關係。