Biomedical subjects

Chin Lung Lu

Publications and source records attributed to Chin Lung Lu.

8 recordsLinked to original sources

PubMed2005

A heuristic approach for detecting RNA H-type pseudoknots.

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. AVAILABILITY: The web server of our HPknotter is available for online analysis at http://bioalgorithm.life.nctu.edu.tw/HPKNOTTER/ CONTACT: cllu@mail.nctu.edu.tw, chiu@cc.nctu.edu.tw

Algorithms↗

PubMed2005

ROBIN: a tool for genome rearrangement of block-interchanges.

SUMMARY: 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.

Algorithms↗

PubMed2005

An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species.

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 Omicron(deltan) time algorithm for solving it by making use of permutation groups in algebra, where n is the length of the circular chromosome and delta is the minimum number of block-interchanges required for the transformation, which can be calculated in Omicron(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.

Algorithms↗

PubMed2004

A memory-efficient algorithm for multiple sequence alignment with constraints.

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 (gamman2) 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. AVAILABILITY: http://genome.life.nctu.edu.tw/MUSICME.

Algorithms↗

PubMed2004

MuSiC: a tool for multiple sequence alignment with constraints.

SUMMARY: 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. AVAILABILITY: http://genome.life.nctu.edu.tw/MUSIC

Algorithms↗

PubMed2004

Evolutionary analysis of the two-component systems in Pseudomonas aeruginosa PAO1.

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.

Base Composition↗

PubMed2003

Constrained multiple sequence alignment tool development and its application to RNase family alignment.

In this paper, we design a heuristic algorithm of computing a constrained multiple sequence alignment (CMSA for short) for guaranteeing that the generated alignment satisfies the user-specified constraints that some particular residues should be aligned together. If the number of residues needed to be aligned together is a constant alpha, then the time-complexity of our CMSA algorithm for aligning K sequences is O(alphaKn(4)), where n is the maximum of the lengths of sequences. In addition, we have built up such a CMSA software system and made several experiments on the RNase sequences, which mainly function in catalyzing the degradation of RNA molecules. The resulting alignments illustrate the practicability of our method.

Algorithms↗

PubMed2002

Constrained multiple sequence alignment tool development and its application to RNase family alignment.

In this paper, we design an algorithm of computing a constrained multiple sequence alignment (CMSA for short) for guaranteeing that the generated alignment satisfies the user-specified constraints that some particular residues should be aligned together. If the number of residues needed to be aligned together is a constant alpha, then the time-complexity of our CMSA algorithm for aligning K sequences is O (alphaKn4), where n is the maximum of the lengths of sequences. In addition, we have build up such a CMSA software system and made several experiments on the RNase sequences, which mainly function in catalyzing the degradation of RNA molecules. The resulting alignments illustrate the practicability of our method.

Algorithms↗