Search PubMed⌕ Search

Biomedical subjects

Chun-Hsi Huang

Publications and source records attributed to Chun-Hsi Huang.

5 recordsLinked to original sources
PubMed2006

Minimotif Miner: a tool for investigating protein function.

In addition to large domains, many short motifs mediate functional post-translational modification of proteins as well as protein-protein interactions and protein trafficking functions. We have constructed a motif database comprising 312 unique motifs and a web-based tool for identifying motifs in proteins. Functional motifs predicted by MnM can be ranked by several approaches, and we validated these scores by analyzing thousands of confirmed examples and by confirming prediction of previously unidentified 14-3-3 motifs in EFF-1.

14-3-3 Proteins↗
PubMed2005

High-performance exact algorithms for motif search.

OBJECTIVE: The human genome project has resulted in the generation of voluminous biological data. Novel computational techniques are called for to extract useful information from this data. One such technique is that of finding patterns that are repeated over many sequences (and possibly over many species). In this paper we study the problem of identifying meaningful patterns (i.e., motifs) from biological data, the motif search problem. METHODS: The general version of the motif search problem is NP-hard. Numerous algorithms have been proposed in the literature to solve this problem. Many of these algorithms fall under the category of heuristics. We concentrate on exact algorithms in this paper. In particular, we concentrate on two different versions of the motif search problem and offer exact algorithms for them. RESULTS: In this paper we present algorithms for two versions of the motif search problem. All of our algorithms are elegant and use only such simple data structures as arrays. For the first version of the problem described as Problem 1 in the paper, we present a simple sorting based algorithm, SMS (Simple Motif Search). This algorithm has been coded and experimental results have been obtained. For the second version of the problem (described in the paper as Problem 2), we present two different algorithms--a deterministic algorithm (called DMS) and a randomized algorithm (Monte Carlo algorithm). We also show how these algorithms can be parallelized. CONCLUSIONS: All the algorithms proposed in this paper are improvements over existing algorithms for these versions of motif search in biological sequence data. The algorithms presented have the potential of performing well in practice.

Algorithms↗
PubMed2005

Randomized and parallel algorithms for distance matrix calculations in multiple sequence alignment.

Multiple sequence alignment (MSA) is a vital problem in biology. Optimal alignment of multiple sequences becomes impractical even for a modest number of sequences since the general version of the problem is NP-hard. Because of the high time complexity of traditional MSA algorithms, even today's fast computers are not able to solve the problem for large number of sequences. In this paper we present a randomized algorithm to calculate distance matrices, which is a major step in many multiple sequence alignment algorithms. The basic idea employed is sampling (along the lines of). We also illustrate how to parallelize this algorithm. In Section we introduce the problem of multiple sequence alignments. In Section we provide a discussion on various methods that have been employed in the literature for Multiple Sequence Alignment. In this section we also introduce our new sampling approach. We extend our randomized algorithm to the case of non-uniform length sequences as well. We show that our algorithms are amenable to parallelism in Section. In Section we back up our claim of speedup and accuracy with empirical data and examples. In Section we provide some concluding remarks.

Algorithms↗
PubMed2003

Parallel pattern identification in biological sequences on clusters.

Tandem repeats are ubiquitous sequence features in both prokaryotic and eukaryotic genomes. They are known to cause several inherited neurological diseases in humans. Identifying these patterns is a highly computation-intensive process. Previous parallel implementations use straightforward domain decomposition based on existing sequential algorithms and rely on parallel machines with low-latency interconnection network and fast hardware support for processor synchronization. Our research exploits the superior cost effectiveness and flexibility achieved through low-cost clusters to speed up biological computations by designing communication-efficient parallel algorithms for pattern identification. This paper presents a low communication-overhead parallel algorithm for pattern identification in biological sequences. Given a biological sequence of length n and a pattern of length m, we conclude an algorithm with five computation/communication phases, each requiring O(n) computation time and only O(p) message units. The low communication overhead of the algorithm is essential in achieving reasonable speedups on clusters, where the inter-processor communication latency is usually higher.

Algorithms↗