Browsing by Author "Lu, CL"

Now showing 1 - 12 of 12

A heuristic approach for detecting RNA H-type pseudoknots
(2005-09-01)
Huang, CH
;
Lu, CL
;
Chiu, HT
;
生物科技學系
;
Department of Biological Science and Technology
Motivation: RNA H-type pseudoknots are ubiquitous pseudoknots that are found in almost all classes of RNA and thought to play very important roles in a variety of biological processes. Detection of these RNA H-type pseudoknots can improve our understanding of RNA structures and their associated functions. However, the currently existing programs for detecting such RNA H-type pseudoknots are still time consuming and sometimes even ineffective. Therefore, efficient and effective tools for detecting the RNA H-type pseudoknots are needed. Results: In this paper, we have adopted a heuristic approach to develop a novel tool, called HPknotter, for efficiently and accurately detecting H-type pseudoknots in an RNA sequence. In addition, we have demonstrated the applicability and effectiveness of HPknotter by testing on some sequences with known H-type pseudoknots. Our approach can be easily extended and applied to other classes of more general pseudoknots.
A memory-efficient algorithm for multiple sequence alignment with constraints
(2005-01-01)
Lu, CL
;
Huang, YP
;
生物科技學系
;
Department of Biological Science and Technology
Motivation: Recently, the concept of the constrained sequence alignment was proposed to incorporate the knowledge of biologists about structures/functionalities/consensuses of their datasets into sequence alignment such that the user-specified residues/nucleotides are aligned together in the computed alignment. The currently developed programs use the so-called progressive approach to efficiently obtain a constrained alignment of several sequences. However, the kernels of these programs, the dynamic programming algorithms for computing an optimal constrained alignment between two sequences, run in O(gamman (2)) memory, where gamma is the number of the constraints and n is the maximum of the lengths of sequences. As a result, such a high memory requirement limits the overall programs to align short sequences only. Results: We adopt the divide-and-conquer approach to design a memory-efficient algorithm for computing an optimal constrained alignment between two sequences, which greatly reduces the memory requirement of the dynamic programming approaches at the expense of a small constant factor in CPU time. This new algorithm consumes only O(alphan) space, where alpha is the sum of the lengths of constraints and usually alpha < n in practical applications. Based on this algorithm, we have developed a memory-efficient tool for multiple sequence alignment with constraints.
An analysis of the combined effects of organic toxicants
(2002-04-22)
Chen, CY
;
Lu, CL
;
環境工程研究所
;
Institute of Environmental Engineering
This paper presents a basic database for the joint actions of 44 binary mixtures of various organic toxicants on Escherichia coli. The multiple toxicity behaviors observed from the E. coli organisms were analyzed and compared with previous works based on the Microtox tests, The two kinds of tests produced quite different responses, in terms of the joint action mode and the sum of toxic units, to various organic mixtures. However, detailed analyses with the considerations of the chemical's mechanisms of toxicity and the slope of toxicant's dose-response curve have revealed several general criteria for the prediction of combined effects of organic toxicants. First, for both reactive and non-reactive toxicants, either additive or less than additive (antagonistic) joint actions will be observed for chemicals of the same mechanism of toxicity. Second, the mixture of reactive toxicants with different mechanisms is the only category of organic mixtures associated with frequent observations of synergism. Third, greater-than-additive (synergistic) effects are inherently associated with toxicants having flat dose-response curves. Less than additive effects are, however, mainly related to a chemical's display steep close-response curves. Model analyses indicate that the observed synergistic effects are due to response addition or response multiplication joint actions. Hence, most of the synergistic joint actions are non-interactive in nature and are governed by the dose-response relationships of individual toxicants. (C) 2002 Elsevier Science B.V. All rights reserved.
An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species
(2005)
Lin, YC
;
Lu, CL
;
Chang, HY
;
Tang, CY
;
生物科技學系
In the study of genome rearrangement, the block-interchanges have been proposed recently as a new kind of global rearrangement events affecting a genome by swapping two nonintersecting segments of any length. The so-called block-interchange distance problem, which is equivalent to the sorting by block-interchange problem, is to find a minimum series of block-interchanges for transforming one chromosome into another. In this paper, we study this problem by considering the circular chromosomes and propose a O(deltan) time algorithm for solving it by making use of permutation groups in algebra, where n is the length of the circular chromosome and 3 is the minimum number of block-interchanges required for the transformation, which can be calculated in O(n) time in advance. Moreover, we obtain analogous results by extending our algorithm to linear chromosomes. Finally, we have implemented our algorithm and applied it to the circular genomic sequences of three human vibrio pathogens for predicting their evolutionary relationships. Consequently, our experimental results coincide with the previous ones obtained by others using a different comparative genomics approach, which implies that the block-interchange events seem to play a significant role in the evolution of vibrio species.
Effects of annealing temperature on electrical resistance of bonded n-GaAs wafers
(2004-11-22)
Liu, PC
;
Lu, CL
;
Wu, YCS
;
Cheng, JH
;
Ouyang, H
The electrical characteristics and microstructures of n-type (100) GaAs bonded interfaces were systematically investigated. Experimental results indicated that GaAs did not bond directly to itself, but via an amorphous oxide layer at 400 degreesC. When temperatures increased above 400 degreesC, the oxide bonded area declined and finally disappeared. Electrical resistance decreased with bonding temperature. However, the resistance increased with temperatures exceeding 850 degreesC. (C) 2004 American Institute of Physics.
Efficient minus and signed domination in graphs
(2003-05-14)
Lu, CL
;
Peng, SL
;
Tang, CY
;
生物科技學系
;
Department of Biological Science and Technology
An efficient minus (respectively, signed) dominating function of a graph G = (V,E) is a function f:V --> {-1,0,1} (respectively, {-1,1}) such that Sigma(uis an element ofN[nu]) f(u) = I for all nu is an element of V, where N [nu] = {nu} boolean OR {u (u, nu) is an element of E}. The efficient minus (respectively, signed) domination problem is to find an efficient minus (respectively, signed) dominating function of G. In this paper, we show that the efficient minus (respectively, signed) domination problem is NP-complete on chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (respectively, on chordal graphs). Based on the forcing property on blocks of vertices and automata theory, we provide a uniform approach to show that in a special class of interval graphs, every graph (respectively, every graph with no vertex of odd degree) has an efficient minus (respectively, signed) dominating function. We also give linear-time algorithms to find these functions. Besides, we show that the efficient minus domination problem is equivalent to the efficient domination problem on trees. (C) 2002 Elsevier Science B.V. All rights reserved.
Evolutionary analysis of the two-component systems in Pseudomonas aeruginosa PAO1
(2004-12-01)
Chen, YT
;
Chang, HY
;
Lu, CL
;
Peng, HL
;
生物科技學系
Gene organization and functional motif analyses of the 123 two-component system (2CS) genes in Pseudomonas aeruginosa PAO1 were carried out. In addition, NJ and ML trees for the sensor kinases and the response regulators were constructed, and the distances measured and comparatively analyzed. It was apparent that more than half of the sensor-regulator gene pairs, especially the 2CSs with OmpR-like regulators, are derivatives of a common ancestor and have most likely co-evolved through gene pair duplication. Several of the 2CS pairs, especially those with NarL-like regulators, however, appeared to be relatively divergent. This is supportive of the recruitment model, in which a sensor gene and regulator gene with different phylogenetic history are assembled to form a 2CS. Correlation of the classification of sensor kinases and response regulators provides further support for these models. Upon comparison of the phylogenetic trees comprised of sensors and regulators, we have identified six congruent clades, which represent the group of the most recently duplicated 2CS gene pairs. Analyses of the congruent 2CS pairs of each of the clades revealed that certain paralogous 2CS pairs may carry a redundant function even after a gene duplication event. Nevertheless, comparative analysis of the putative promoter regions of the paralogs suggested that functional redundancy could be prevented by a differential control. Both codon usage and G+C content of these 2CS genes were found to be comparable with those of the P. aeruginosa genome, suggesting that they are not newly acquired genes.
MuSiC: a tool for multiple sequence alignment with constraints
(2004-09-22)
Tsai, YT
;
Huang, YP
;
Yu, CT
;
Lu, CL
;
生物科技學系
MuSiC is a web server to perform the constrained alignment of a set of sequences, such that the user-specified residues/nucleotides are aligned with each other. The input of the MuSiC system consists of a set of protein/DNA/RNA sequences and a set of user-specified constraints, each with a fragment of residue/nucleotide that (approximately) appears in all input sequences. The output of MuSiC is a constrained multiple sequence alignment in which the fragments of the input sequences whose residues/nucleotides exhibit a given degree of similarity to a constraint are aligned together. The current MuSiC system is implemented in Java language and can be accessed via a simple web interface.
On the full and bottleneck full Steiner tree problems
(2003)
Chen, YH
;
Lu, CL
;
Tang, CY
;
生物科技學系
;
Department of Biological Science and Technology
Given a graph G = (V, E) with a length function on edges and a subset R of V, the full Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. Then the full Steiner tree problem is to find a full Steiner tree in G with minimum length, and the bottleneck full Steiner tree problem is to find a full Steiner tree T in G such that the length of the largest edge in T is minimized. In this paper, we present a new approximation algorithm with performance ratio 2p for the full Steiner tree problem, where p is the best-known performance ratio for the Steiner tree problem. Moreover, we give an exact algorithm of O(E log E) time to solve the bottleneck full Steiner tree problem.
ROBIN: a tool for genome rearrangement of block-interchanges
(2005-06-01)
Lu, CL
;
Wang, TC
;
Lin, YC
;
Tang, CY
;
生物科技學系
ROBIN is a web server for analyzing genome rearrangement of block-interchanges between two chromosomal genomes. It takes two or more linear/circular chromosomes as its input, and computes the number of minimum block-interchange rearrangements between any two input chromosomes for transforming one chromosome into another and also determines an optimal scenario taking this number of rearrangements. The input can be either bacterial-size sequence data or landmark-order data. If the input is sequence data, ROBIN will automatically search for the identical landmarks that are the homologous/conserved regions shared by all the input sequences.
The approximability of the weighted Hamiltonian path completion problem on a tree
(2005-09-05)
Wu, Q
;
Lu, CL
;
Lee, RCT
;
生物科技學系
;
Department of Biological Science and Technology
Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem remains hard to approximate even when the given subgraph is a tree. Moreover, if the edge weights are restricted to be either 1 or 2, the Hamiltonian path completion problem on a tree is still NP-hard. Then it is observed that this problem is strongly NP-hard, so it does not have any fully polynomial-time approximation scheme (FPTAS) unless NP = P. When the given tree is a k-tree, we give an approximation algorithm with performance ratio 1.5. (c) 2005 Elsevier B.V. All rights reserved.
The full Steiner tree problem
(2003-09-05)
Lu, CL
;
Tang, CY
;
Lee, RCT
;
生物科技學系
;
Department of Biological Science and Technology
Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V, E) with a length function on E and a proper subset R subset of V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either I or 2. For the instances with lengths either I or 2, we give a 8/5-approximation algorithm to find an approximate solution for the problem. (C) 2003 Elsevier B.V. All rights reserved.