Please use this identifier to cite or link to this item:
Homologous Synteny Block Detection and Recognition Based on Suffix Tree Algorithms
|Authors: ||Yu-Lun Chen|
|Contributors: ||NTOU:Department of Computer Science and Engineering|
collinear;synteny block;suffix tree;orthologous gene;phylogenetic tree
|Issue Date: ||2013-10-07T02:59:23Z
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.
|Appears in Collections:||[資訊工程學系] 博碩士論文|
Files in This Item:
All items in NTOUR are protected by copyright, with all rights reserved.