Browsing by Author "Tang, Chuan Yi"

Now showing 1 - 14 of 14

An improved algorithm for finding a length-constrained maximum-density subtree in a tree
(2008-12-31)
Su, Hsin-Hao
;
Lu, Chin Lung
;
Tang, Chuan Yi
;
生物科技學系
;
生物資訊及系統生物研究所
Given a tree T with weight and length on each edge, as well as a lower bound L and an upper bound U, the so-called length-constrained maximum-density subtree problem is to find a maximum-density subtree in T such that the length of this subtree is between L and U. In this study, we present an algorithm that runs in O (nU log n) time for the case when the edge lengths are positive integers, where n is the number of nodes in T, which is an improvement over the previous algorithms when U = Omega(log n). In addition, we show that the time complexity Of Our algorithm can be reduced to (nL log n/L), when the edge lengths being considered are uniform. (C) 2008 Elsevier B.V. All rights reserved.
An improved algorithm for sorting by block-interchanges based on permutation groups
(2010-04-01)
Huang, Yen-Lin
;
Huang, Cheng-Chen
;
Tang, Chuan Yi
;
Lu, Chin Lung
;
生物科技學系
Given a chromosome represented by a permutation of genes, a block-interchange is proposed as a generalized transposition that affects the chromosome by swapping two non-intersecting segments of genes. The problem of sorting by block-interchanges is to find a minimum series of block-interchanges for sorting one chromosome into another. In this paper, we present an O(n + delta log delta) time algorithm for solving the problem of sorting by block-interchanges, which improves a previous algorithm of O(delta n) time proposed by Lin et al. (2005) [14], where n is the number of genes and delta is the minimum number of block-interchanges required to sort a chromosome. (C) 2010 Elsevier B.V. All rights reserved.
CAPS Genomic Subtyping on Orthomyxoviridae
(2009)
Peng, Sheng-Lung
;
Tsay, Yu-Wei
;
Lin, Chich-Sheng
;
Tang, Chuan Yi
;
生物科技學系
The Orthomyxoviridae is a family of single strained RNA viruses including five genera: Influenza virus A, Influenza virus B, Influenza virus C, Thogotovirus, and Isavirus. Usually, Influenza viruses are identified by antigenic differences in their nucleoprotein and matrix protein. In this paper, we propose an algorithm to determine a set of suitable: restriction enzymes for producing recognizable restriction maps on Orthomyxoviridae. Our method is applied to viral strains of highly pathogenic avian influenza (HPAI), containing potentially homozygous, heterozygous; and various genetic variations. In the analysis of CAPS (Cleaved Amplified Polymorphic Sequence) subtyping, our method out; performs the RNA coding of representative and epidemiologically significant human wild-type viruses, including H3N8, H5N1, H5N9, H7N1, H7N7, and H9N2. These isolates are analyzed by CAPS with enzymes Agel, EciI, KpnI, and XbaI. The HPAI strains show a. different RFLP (Restriction Fragment Length Polymorphism) profile by comparing with other low pathogenic avian influenza (LPAI) strains. We provide a rapid; specific, and reproducible identification of the genotypes on Orthomyxoviridae It permits us to quickly confirm subtypes of Orthomyxoviridae.
Constrained sequence alignment: A general model and the hardness results
(2007-11-01)
Chung, Yun-Sheng
;
Lu, Chin Lung
;
Tang, Chuan Yi
;
生物科技學系
;
Department of Biological Science and Technology
Imposing constraints is a way to incorporate information into the sequence alignment procedure. In this paper, a general model for constrained alignment is proposed so that analyses admitted are more flexible and that different pattern definitions can be treated in a simple unified way. We give a polynomial time algorithm for pairwise constrained alignment for the generalized formulation, and prove the inapproximability of the problem when the number of sequences can be arbitrary. In addition, previous works deal only with the case that the patterns in the constraint have to occur in the output alignment in the same order as that specified by the input. It is of both theoretical and practical interest to investigate the case when the order is no longer limited. We show that the problem is not approximable even when the number of sequences is two. We also give the NPO-completeness results for the problems with bounds imposed on the objective function value. (c) 2007 Elsevier B.V. All rights reserved.
Detection and Alignment of 3D Domain Swapping Proteins Using Angle-Distance Image-Based Secondary Structural Matching Techniques
(2010-10-14)
Chu, Chia-Han
;
Lo, Wei-Cheng
;
Wang, Hsin-Wei
;
Hsu, Yen-Chu
;
Hwang, Jenn-Kang
This work presents a novel detection method for three-dimensional domain swapping (DS), a mechanism for forming protein quaternary structures that can be visualized as if monomers had "opened'' their "closed'' structures and exchanged the opened portion to form intertwined oligomers. Since the first report of DS in the mid 1990s, an increasing number of identified cases has led to the postulation that DS might occur in a protein with an unconstrained terminus under appropriate conditions. DS may play important roles in the molecular evolution and functional regulation of proteins and the formation of depositions in Alzheimer's and prion diseases. Moreover, it is promising for designing auto-assembling biomaterials. Despite the increasing interest in DS, related bioinformatics methods are rarely available. Owing to a dramatic conformational difference between the monomeric/closed and oligomeric/open forms, conventional structural comparison methods are inadequate for detecting DS. Hence, there is also a lack of comprehensive datasets for studying DS. Based on angle-distance (A-D) image transformations of secondary structural elements (SSEs), specific patterns within A-D images can be recognized and classified for structural similarities. In this work, a matching algorithm to extract corresponding SSE pairs from A-D images and a novel DS score have been designed and demonstrated to be applicable to the detection of DS relationships. The Matthews correlation coefficient (MCC) and sensitivity of the proposed DS-detecting method were higher than 0.81 even when the sequence identities of the proteins examined were lower than 10%. On average, the alignment percentage and root-mean-square distance (RMSD) computed by the proposed method were 90% and 1.8 angstrom for a set of 1,211 DS-related pairs of proteins. The performances of structural alignments remain high and stable for DS-related homologs with less than 10% sequence identities. In addition, the quality of its hinge loop determination is comparable to that of manual inspection. This method has been implemented as a web-based tool, which requires two protein structures as the input and then the type and/or existence of DS relationships between the input structures are determined according to the A-D image-based structural alignments and the DS score. The proposed method is expected to trigger large-scale studies of this interesting structural phenomenon and facilitate related applications.
Efficient algorithms for regular expression constrained sequence alignment
(2007-09-15)
Chung, Yun-Sheng
;
Lu, Chin Lung
;
Tang, Chuan Yi
;
生物科技學系
;
Department of Biological Science and Technology
Imposing constraints is an effective means to incorporate biological knowledge into alignment procedures. As in the PROSITE database, functional sites of proteins can be effectively described as regular expressions. In an alignment of protein sequences it is natural to expect that functional motifs should be aligned together. Due to this motivation, Arslan introduced the regular expression constrained sequence alignment problem and proposed an algorithm which, if implemented naively, can take time and space up to O(vertical bar Sigma vertical bar V-2 vertical bar vertical bar(4)n(2)) and O(vertical bar Sigma vertical bar(2)vertical bar V vertical bar(4)n), respectively, where Sigma is the alphabet, n is the sequence length, and V is the set of states in an automaton equivalent to the input regular expression. In this paper we propose a more efficient algorithm solving this problem which takes O(vertical bar V vertical bar(3)n(2)) time and O(vertical bar V vertical bar(2n)) space in the worst case. If vertical bar V vertical bar = O(log n) we propose another algorithm with time complexity O(vertical bar V vertical bar(2)log vertical bar V vertical bar n(2)). The time complexity of our algorithms is independent of Sigma, which is desirable in protein applications where the formulation of this problem originates; a factor of vertical bar Sigma vertical bar(2) = 400 in the time complexity of the previously proposed algorithm would significantly affect the efficiency in practice. (c) 2007 Elsevier B.V All rights reserved.
Efficient algorithms for regular expression constrained sequence alignment
(2006)
Chung, Yun-Sheng
;
Lu, Chin Lung
;
Tang, Chuan Yi
;
生物科技學系
;
Department of Biological Science and Technology
Imposing constraints is an effective means to incorporate biological knowledge into alignment procedures. As in the PROSITE database, functional sites of proteins can be effectively described as regular expressions. In an alignment of protein sequences it is natural to expect that functional motifs should be aligned together. Due to this motivation, in CPM 2005 Arslan introduced the regular expression constrained sequence alignment problem and proposed an algorithm which can take time and space up to O(vertical bar Sigma vertical bar(2) vertical bar V vertical bar(4) n(2)) and O(vertical bar Sigma vertical bar(2) vertical bar V vertical bar(4)n), respectively, where Sigma is the alphabet, n is the sequence length, and V is the set of states in an automaton equivalent to the input regular expression. In this paper we propose a more efficient algorithm solving this problem which takes O(vertical bar V vertical bar(3) n(2)) time and O(vertical bar V vertical bar(2) n) space in the worst case. If vertical bar V vertical bar = O(log n) we propose another algorithm with time complexity O(vertical bar V vertical bar(2) log vertical bar V vertical bar n(2)). The time complexity of our algorithms is independent of Sigma, which is desirable in protein applications where the formulation of this problem originates; a factor of vertical bar Sigma vertical bar(2) = 400 in the time complexity of the previously proposed algorithm would significantly affect the efficiency in practice.
Enzyme Reaction Annotation Using Cloud Techniques
(2013)
Huang, Chuan-Ching
;
Lin, Chun-Yuan
;
Chang, Cheng-Wen
;
Tang, Chuan Yi
;
應用化學系
An understanding of the activities of enzymes could help to elucidate the metabolic pathways of thousands of chemical reactions that are catalyzed by enzymes in living systems. Sophisticated applications such as drug design and metabolic reconstruction could be developed using accurate enzyme reaction annotation. Because accurate enzyme reaction annotation methods create potential for enhanced production capacity in these applications, they have received greater attention in the global market. We propose the enzyme reaction prediction (ERP) method as a novel tool to deduce enzyme reactions from domain architecture. We used several frequency relationships between architectures and reactions to enhance the annotation rates for single and multiple catalyzed reactions. The deluge of information which arose from high-throughput techniques in the postgenomic era has improved our understanding of biological data, although it presents obstacles in the data-processing stage. The high computational capacity provided by cloud computing has resulted in an exponential growth in the volume of incoming data. Cloud services also relieve the requirement for large-scale memory space required by this approach to analyze enzyme kinetic data. Our tool is designed as a single execution file; thus, it could be applied to any cloud platform in which multiple queries are supported.
Feature selection and combination criteria for improving accuracy in protein structure prediction
(2007-06-01)
Lin, Ken-Li
;
Lin, Chun-Yuan
;
Huang, Chuen-Der
;
Chang, Hsiu-Ming
;
Yang, Chiao-Yun
The classification of protein structures is essential for their function determination in bioinformatics. At present, a reasonably high rate of prediction accuracy has been achieved in classifying proteins into four classes in the SCOP database according to their primary amino acid sequences. However, for further classification into fine-grained folding categories, especially when the number of possible folding patterns as those defined in the SCOP database is large, it is still quite a challenge. In our previous work, we have proposed a two-level classification strategy called hierarchical learning architecture (HLA) using neural networks and two indirect coding features to differentiate proteins according to their classes and folding patterns, which achieved an accuracy rate of 65.5%. In this paper, we use a combinatorial fusion technique to facilitate feature selection and combination for improving predictive accuracy in protein structure classification. When applying various criteria in combinatorial fusion to the protein fold prediction approach using neural networks with HLA and the radial basis function network (RBFN), the resulting classification has an overall prediction accuracy rate of 87% for four classes and 69.6% for 27 folding categories. These rates are significantly higher than the accuracy rate of 56.5% previously obtained by Ding and Dubchak. Our results demonstrate that data fusion is a viable method for feature selection and combination in the prediction and classification of protein structure.
GI-POP: A combinational annotation and genomic island prediction pipeline for ongoing microbial genome projects
(2013-04-10)
Lee, Chi-Ching
;
Chen, Yi-Ping Phoebe
;
Yao, Tzu-Jung
;
Ma, Cheng-Yu
;
Lo, Wei-Cheng
Sequencing of microbial genomes is important because of microbial-carrying antibiotic and pathogenetic activities. However, even with the help of new assembling software, finishing a whole genome is a time-consuming task. In most bacteria, pathogenetic or antibiotic genes are carried in genomic islands. Therefore, a quick genomic island (GI) prediction method is useful for ongoing sequencing genomes. In this work, we built a Web server called GI-POP (http://gipop.life.nthu.edu.tw) which integrates a sequence assembling tool, a functional annotation pipeline, and a high-performance GI predicting module, in a support vector machine (SVM)-based method called genomic island genomic profile scanning (GI-GPS). The draft genomes of the ongoing genome projects in contigs or scaffolds can be submitted to our Web server, and it provides the functional annotation and highly probable GI-predicting results. GI-POP is a comprehensive annotation Web server designed for ongoing genome project analysis. Researchers can perform annotation and obtain pre-analytic information include possible GIs, coding/non-coding sequences and functional analysis from their draft genomes. This pre-analytic system can provide useful information for finishing a genome sequencing project. (c) 2012 Elsevier B.V. All rights reserved.
Identification of Essential Residues of Human alpha-L-Fucosidase and Tests of Its Mechanism
(2009-01-13)
Liu, Sheng-Wen
;
Chen, Chao-Sheng
;
Chang, Shih-Shen
;
Mong, Kwok-Kong Tony
;
Lin, Chun-Hung
Fucosylated glycoconjugates have critical roles in biological processes, but a limited availability Of alpha-L-fucosidase has hampered research on this human enzyme (h-Fuc) at a molecular level. After overexpressing h-Fuc in Escherichia coli as an active form, we investigated the catalytic function of this recombinant enzyme. Based on sequence alignment and structural analysis of close homologues of h-Fuc, nine residues of glutamate and aspartate in h-Fuc were selected for mutagenic tests to determine the essential residues. Among the mutants, D225N, E289Q, and E289G lost catalytic activity significantly; their k(cat) values are 1/5700, 1/430, and 1/340, respectively, of that of the wild-type enzyme. The Bronsted plot for k(cat)/K(m) for the E289G mutant is linear with beta(1g) = -0.93, but that for k(cat) is biphasic, with beta(1g) for poor substrates being -0.88 and for activated substrates being -0.11. The small magnitude of Pig for the activated substrates may indicate that the rate-limiting step of the reaction is defucosylation, whereas the large magnitude of the latter Pig value for the poor substrates indicates that the rate-limiting step of the reaction becomes fucosylation. The kinetic outcomes support an argument that ASp(225) functions as a nucleophile and Glu(289) as a general acid/base catalyst. As further evidence, azide significantly reactivated D225G and E289G, and (1)H NMR spectral analysis confirmed the formation of beta-fucosyl azide and alpha-fucosyl azide in the azide rescues of D225G and E289G catalyses, respectively. As direct evidence to prove the function of Glu(289), an accumulation of fucosyl-enzyme intermediate was detected directly through ESI/MS analysis.
RE-MuSiC: a tool for multiple sequence alignment with regular expression constraints
(2007-07-01)
Chung, Yun-Sheng
;
Lee, Wei-Hsun
;
Tang, Chuan Yi
;
Lu, Chin Lung
;
生物科技學系
RE-MuSiC is a web-based multiple sequence alignment tool that can incorporate biological knowledge about structure, function, or conserved patterns regarding the sequences of interest. It accepts amino acid or nucleic acid sequences and a set of constraints as inputs. The constraints are pattern descriptions, instead of exact positions of fragments to be aligned together. The output is an alignment where for each pattern (constraint), an occurrence on each sequence can be found aligned together with those on the other sequences, in a manner that the overall alignment is optimized. Its predecessor, MuSiC, has been found useful by researchers since its release in 2004. However, it is noticed in applications that the pattern formulation adopted in MuSiC, namely, plain strings allowing mismatches, is not expressive and flexible enough. The constraint formulation adopted in RE-MuSiC is therefore enhanced to be regular expressions, which is convenient in expressing many biologically significant patterns like those collected in the PROSITE database, or structural consensuses that often involve variable ranges between conserved parts. Experiments demonstrate that RE-MuSiC can be used to help predict important residues and locate phylogenetically conserved structural elements. RE-MuSiC is available on-line at http://140.113.239.131/RE-MUSIC.
SoRT(2): a tool for sorting genomes and reconstructing phylogenetic trees by reversals, generalized transpositions and translocations
(2010-07-01)
Huang, Yen-Lin
;
Huang, Chen-Cheng
;
Tang, Chuan Yi
;
Lu, Chin Lung
;
生物科技學系
SoRT(2) is a web server that allows the user to perform genome rearrangement analysis involving reversals, generalized transpositions and translocations (including fusions and fissions), and infer phylogenetic trees of genomes being considered based on their pairwise genome rearrangement distances. It takes as input two or more linear/circular multi-chromosomal gene (or synteny block) orders in FASTA-like format. When the input is two genomes, SoRT(2) will quickly calculate their rearrangement distance, as well as a corresponding optimal scenario by highlighting the genes involved in each rearrangement operation. In the case of multiple genomes, SoRT(2) will also construct phylogenetic trees of these genomes based on a matrix of their pairwise rearrangement distances using distance-based approaches, such as neighbor-joining (NJ), unweighted pair group method with arithmetic mean (UPGMA) and Fitch-Margoliash (FM) methods. In addition, if the function of computing jackknife support values is selected, SoRT(2) will further perform the jackknife analysis to evaluate statistical reliability of the constructed NJ, UPGMA and FM trees. SoRT(2) is available online at http://bioalgorithm.life.nctu.edu.tw/SORT2/.
SPRING: a tool for the analysis of genome rearrangement using reversals and block-interchanges
(2006-07-01)
Lin, Ying Chih
;
Lu, Chin Lung
;
Liu, Ying-Chuan
;
Tang, Chuan Yi
;
生物科技學系
SPRING( http://algorithm.cs.nthu.edu.tw/tools/SPRING/)is a tool for the analysis of genome rearrangement between two chromosomal genomes using reversals and/ or block- interchanges. SPRING takes two ormore chromosomes as its input and then computes a minimum series of reversals and/ or block-interchanges between any two input chromosomes for transforming one chromosome into another. The input of SPRING can be either bacterial- size sequences or gene/ landmark orders. If the input is a set of chromosomal sequences then the SPRING will automatically search for identical landmarks, which are homologous/ conserved regions shared by all input sequences. In particular, SPRING also computes the breakpoint distance between any pair of two chromosomes, which can be used to compare with the rearrangement distance to confirm whether they are correlated or not. In addition, SPRING shows phylogenetic trees that are reconstructed based on the rearrangement and breakpoint distance matrixes.