English  |  正體中文  |  简体中文  |  Items with full text/Total items : 26988/38789
Visitors : 2343452      Online Users : 29
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search
LoginUploadHelpAboutAdminister

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/35806

Title: 基於後綴樹演算法之同源共線性區塊偵測與辨識
Homologous Synteny Block Detection and Recognition Based on Suffix Tree Algorithms
Authors: Yu-Lun Chen
陳煜倫
Contributors: NTOU:Department of Computer Science and Engineering
國立臺灣海洋大學:資訊工程學系
Keywords: 共線性;共線性區塊;後綴樹;同源基因;演化樹
collinear;synteny block;suffix tree;orthologous gene;phylogenetic tree
Date: 2013
Issue Date: 2013-10-07T02:59:23Z
Abstract: 同源共線性區塊是指跨物種間各自保留在某一個染色體之連續基因區段。經過長時間的演化過程與多次的基因體重組,這些共線性區塊依然擁有高度的保留性。了解與探討共線性區塊的分布能協助生物學家追朔生命之起源與多樣性,且這些共線性區塊的保留特徵更在同源基因的辨識與基因標註扮演重要角色。本論文主要目的是偵測與辨識跨物種之間所有存在基因連續且順序相同之共線性區塊。為能有效偵測共線性區塊,本論文提出一套以後綴樹演算法為基礎的同源共線性區塊偵測與辨識。基於傳統後綴樹演算法以字串建構後綴樹的概念,本論文經改良後將每一個染色體視為獨立之字串,而存在於染色體內的每一個基因則分別視為單一字母,再透過同源基因的關聯性建構相對應的後綴樹,藉由後綴樹之特性,可以同時將多個物種建構於單一的後綴樹結構。一旦後綴樹建構完成,再檢驗後綴樹各個邊的重疊情形,可進行快速有效的共線性區塊偵測。此外,本研究也提出一套共線性區塊保留指標的量化公式,透過兩物種彼此間的共線性區塊保留分布,估算物種間的演化關係進而建構物種演化樹,相較於傳統耗時的全基因組序列排比方式更能有效觀察物種間的演化關聯性。
A synteny block represents a set of contiguous genes located within the same chromosome and well conserved among various species. Through long evolutionary processes and genome rearrangement events, large numbers of synteny blocks remain highly conserved across multiple species. Understanding distribution of conserved gene blocks facilitates evolutionary biologists to trace the origin and diversity of life, and it also plays an important role for orthologous gene identification and gene annotation in the genomic era. In this work we focus on collinear synteny detection in which the order of genes is required and well conserved among multiple species. To achieve this goal a suffix tree based algorithm for efficiently and effectively identifying homologous synteny blocks was proposed. The traditional suffix tree algorithm was modified by considering a chromosome as a string and each gene in the chromosome is encoded as a symbol character. Hence, a suffix tree can be built for different query chromosomes from various species. We could then effectively search for conserved synteny blocks that are modeled as overlapped contiguous edges in the constructed suffix tree. In addition, we defined a novel Synteny Block Conserved Index (SBCI) to evaluate the relationship of synteny block distribution between two species, which could be applied as an evolutionary indicator for constructing a phylogenetic tree from multiple species to avoid large computational requirements through whole genome sequence alignment.
URI: http://ethesys.lib.ntou.edu.tw/cdrfb3/record/#G0010057025
http://ntour.ntou.edu.tw/handle/987654321/35806
Appears in Collections:[資訊工程學系] 博碩士論文

Files in This Item:

File Description SizeFormat
index.html0KbHTML119View/Open


All items in NTOUR are protected by copyright, with all rights reserved.

 


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback