Browsing by Author "Yang, Chung-Han"

Now showing 1 - 7 of 7

Approximate String Matching Problem under Non-Overlapping Inversion Distance
(2015-01-01)
Huang, Shih-Yuan
;
Yang, Chung-Han
;
Ta, Toan Thang
;
Lu, Chin Lung
;
生物資訊及系統生物研究所
In this paper, we introduce and study the approximate string matching problem under non-overlapping inversion distance. Given a text t, a pattern p and a non-negative integer k, the goal of the problem is to find all locations in the text t that match the pattern p with at most k non-overlapping inversions. As a result, we use the dynamic programming approach to design an algorithm that solves this problem in O(nm(2)) time and O(m(2)) space, where n is the length of the text and m is the length of the pattern.
Efficient method and apparatus for convolution of input signals
(2005-10-06)
Liu, Chi-Min
;
Lee, Win-Chieh
;
Yang, Chung-Han
An FIR-based apparatus performs fast convolution in the frequency domain for generating room reverberation. The impulse response of a room is segmented and transformed by FFT to form a plurality of segmented room frequency spectra. The input signal to the room is also segmented and transformed to form segmented input frequency spectra. Either overlap-and-add method or overlap-and-save method is applied in the apparatus to accomplish the fast convolution based on the multiplication of segmented input frequency spectrum and segmented room frequency spectrum. To further reduce the complexity of the convolution, a segmented room frequency spectrum is processed to remove high frequency components before being used in the fast convolution according to a perceptual criterion.
iPARTS2: an improved tool for pairwise alignment of RNA tertiary structures, version 2
(2016-07-08)
Yang, Chung-Han
;
Shih, Cheng-Ting
;
Chen, Kun-Tze
;
Lee, Po-Han
;
Tsai, Ping-Han
Since its first release in 2010, iPARTS has become a valuable tool for globally or locally aligning two RNA 3D structures. It was implemented by a structural alphabet (SA)-based approach, which uses an SA of 23 letters to reduce RNA 3D structures into 1D sequences of SA letters and applies traditional sequence alignment to these SA-encoded sequences for determining their global or local similarity. In this version, we have re-implemented iPARTS into a new web server iPARTS2 by constructing a totally new SA, which consists of 92 elements with each carrying both information of base and backbone geometry for a representative nucleotide. This SA is significantly different from the one used in iPARTS, because the latter consists of only 23 elements with each carrying only the backbone geometry information of a representative nucleotide. Our experimental results have shown that iPARTS2 outperforms its previous version iPARTS and also achieves better accuracy than other popular tools, such as SARA, SETTER and RASS, in RNA alignment quality and function prediction. iPARTS2 takes as input two RNA 3D structures in the PDB format and outputs their global or local alignments with graphical display. iPARTS2 is now available online at http://genome.cs.nthu.edu.tw/iPARTS2/.
Prefix Block-Interchanges on Binary Strings
(2015-01-01)
Chou, Shih-Wen
;
Yang, Chung-Han
;
Chen, Kun-Tze
;
Lu, Chin Lung
;
生物資訊及系統生物研究所
A block-interchange acting on a string s exchanges two non-overlapping but not necessary adjacent substrings in s. A prefix block-interchange is a special block-interchange in which one of the two exchanged substrings is restricted to a prefix of s. In this study, we study the problem of sorting by prefix block-interchanges on binary strings, which is to find the minimum number of prefix block-interchanges to sort a given binary string. In addition, we study the problem of computing the prefix block-interchange distance between two binary strings, which is to compute the minimum number of prefix block-interchanges to transform a given binary string into another given binary string. Consequently, we design a linear-time algorithm to solve the problem of sorting by prefix block-interchange on binary strings and also show that the problem of computing the prefix block-interchange distance between two binary strings is NP-hard.
R3D-BLAST: a search tool for similar RNA 3D substructures
(2011-07-01)
Liu, Yun-Chen
;
Yang, Chung-Han
;
Chen, Kun-Tze
;
Wang, Jyun-Rong
;
Cheng, Mei-Ling
R3D-BLAST is a BLAST-like search tool that allows the user to quickly and accurately search against the PDB for RNA structures sharing similar substructures with a specified query RNA structure. The basic idea behind R3D-BLAST is that all the RNA 3D structures deposited in the PDB are first encoded as 1D structural sequences using a structural alphabet of 23 distinct nucleotide conformations, and BLAST is then applied to these 1D structural sequences to search for those RNA substructures whose 1D structural sequences are similar to that of the query RNA substructure. R3D-BLAST takes as input an RNA 3D structure in the PDB format and outputs all substructures of the hits similar to that of the query with a graphical display to show their structural superposition. In addition, each RNA substructure hit found by R3D-BLAST has an associated E-value to measure its statistical significance. R3D-BLAST is now available online at http://genome.cs.nthu.edu.tw/R3D-BLAST/ for public access.
Reconstructing genome trees of prokaryotes using overlapping genes
(2010-02-24)
Cheng, Chih-Hsien
;
Yang, Chung-Han
;
Chiu, Hsien-Tai
;
Lu, Chin Lung
;
生物科技學系
Background: Overlapping genes (OGs) are defined as adjacent genes whose coding sequences overlap partially or entirely. In fact, they are ubiquitous in microbial genomes and more conserved between species than nonoverlapping genes. Based on this property, we have previously implemented a web server, named OGtree, that allows the user to reconstruct genome trees of some prokaryotes according to their pairwise OG distances. By analogy to the analyses of gene content and gene order, the OG distance between two genomes we defined was based on a measure of combining OG content (i.e., the normalized number of shared orthologous OG pairs) and OG order (i.e., the normalized OG breakpoint distance) in their whole genomes. A shortcoming of using the concept of breakpoints to define the OG distance is its inability to analyze the OG distance of multi-chromosomal genomes. In addition, the amount of overlapping coding sequences between some distantly related prokaryotic genomes may be limited so that it is hard to find enough OGs to properly evaluate their pairwise OG distances. Results: In this study, we therefore define a new OG order distance that is based on more biologically accurate rearrangements (e. g., reversals, transpositions and translocations) rather than breakpoints and that is applicable to both uni-chromosomal and multi-chromosomal genomes. In addition, we expand the term "gene" to include both its coding sequence and regulatory regions so that two adjacent genes whose coding sequences or regulatory regions overlap with each other are considered as a pair of overlapping genes. This is because overlapping of regulatory regions of distinct genes suggests that the regulation of expression for these genes should be more or less interrelated. Based on these modifications, we have reimplemented our OGtree as a new web server, named OGtree2, and have also evaluated its accuracy of genome tree reconstruction on a testing dataset consisting of 21 Proteobacteria genomes. Our experimental results have finally shown that our current OGtree2 indeed outperforms its previous version OGtree, as well as another similar server, called BPhyOG, significantly in the quality of genome tree reconstruction, because the phylogenetic tree obtained by OGtree2 is greatly congruent with the reference tree that coincides with the taxonomy accepted by biologists for these Proteobacteria. Conclusions: In this study, we have introduced a new web server OGtree2 at http://bioalgorithm.life.nctu.edu.tw/ OGtree2.0/ that can serve as a useful tool for reconstructing more precise and robust genome trees of prokaryotes according to their overlapping genes.
Reconstructing genome trees of prokaryotes using overlapping genes
(2010-02-24)
Cheng, Chih-Hsien
;
Yang, Chung-Han
;
Chiu, Hsien-Tai
;
Lu, Chin Lung
;
生物科技學系
Background: Overlapping genes (OGs) are defined as adjacent genes whose coding sequences overlap partially or entirely. In fact, they are ubiquitous in microbial genomes and more conserved between species than nonoverlapping genes. Based on this property, we have previously implemented a web server, named OGtree, that allows the user to reconstruct genome trees of some prokaryotes according to their pairwise OG distances. By analogy to the analyses of gene content and gene order, the OG distance between two genomes we defined was based on a measure of combining OG content (i.e., the normalized number of shared orthologous OG pairs) and OG order (i.e., the normalized OG breakpoint distance) in their whole genomes. A shortcoming of using the concept of breakpoints to define the OG distance is its inability to analyze the OG distance of multi-chromosomal genomes. In addition, the amount of overlapping coding sequences between some distantly related prokaryotic genomes may be limited so that it is hard to find enough OGs to properly evaluate their pairwise OG distances. Results: In this study, we therefore define a new OG order distance that is based on more biologically accurate rearrangements (e. g., reversals, transpositions and translocations) rather than breakpoints and that is applicable to both uni-chromosomal and multi-chromosomal genomes. In addition, we expand the term "gene" to include both its coding sequence and regulatory regions so that two adjacent genes whose coding sequences or regulatory regions overlap with each other are considered as a pair of overlapping genes. This is because overlapping of regulatory regions of distinct genes suggests that the regulation of expression for these genes should be more or less interrelated. Based on these modifications, we have reimplemented our OGtree as a new web server, named OGtree2, and have also evaluated its accuracy of genome tree reconstruction on a testing dataset consisting of 21 Proteobacteria genomes. Our experimental results have finally shown that our current OGtree2 indeed outperforms its previous version OGtree, as well as another similar server, called BPhyOG, significantly in the quality of genome tree reconstruction, because the phylogenetic tree obtained by OGtree2 is greatly congruent with the reference tree that coincides with the taxonomy accepted by biologists for these Proteobacteria. Conclusions: In this study, we have introduced a new web server OGtree2 at http://bioalgorithm.life.nctu.edu.tw/ OGtree2.0/ that can serve as a useful tool for reconstructing more precise and robust genome trees of prokaryotes according to their overlapping genes.