LCLiming Cai

Liming Cai

*This is an algorithmically generated author record based on publicly available information.

Liming Cai has a total of 67 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • A New Graph Theoretic Approach for Protein Threading

    by Yinglei Song, Junfeng Qu, Ying Xu, Liming Cai

    In this paper, we develop a novel graph theoretic approach for protein threading. In order to perform the protein sequence-structure alignment in threading both efficiently and accurately, we develop a graph model to describe the tertiary structure of a protein family and the alignment between a sequence and a family can be efficiently computed with a dynamic programming algorithm when the tree width of the graph model is a small integer. Our experiments show that this new approach is significantly faster than existing tools for threading and can achieve comparable prediction accuracy.


  • Open Access

    Accurate prediction of RNA nucleotide interactions with backbone k-tree model

    by Liang Ding, Xingran Xue, Sal LaMarca, Mohammad Mohebbi, Abdul Samad, Russell L. Malmberg, Liming Cai

    Motivation: Given the importance of non-coding RNAs to cellular regulatory functions, it would be highly desirable to have accurate computational prediction of RNA 3D structure, a task which remains challenging. Even for a short RNA sequence, the space of tertiary conformations is immense; existing methods to identify native-like conformations mostly resort to random sampling of conformations to achieve computational feasibility. However, native conformations may not be examined and prediction accuracy may be compromised due to sampling. State-of-the-art methods have yet to deliver satisfactory predictions for RNAs of length beyond 50 nucleotides. Results: This paper presents a method to tackle a key step in the RNA 3D structure prediction problem, the prediction of the nucleotide interactions that constitute the desired 3D structure. The research is based on a novel graph model, called a backbone k-tree, to tightly constrain the nucleotide interaction relationships considered for RNA 3D structures. It is shown that the new model makes it possible to efficiently predict the optimal set of nucleotide interactions (including the non-canonical interactions in all recently revealed families) from the query sequence along with known or predicted canonical basepairs. The preliminary results indicate that in most cases the new method can predict with a high accuracy the nucleotide interactions that constitute the 3D structure of the query sequence. It thus provides a useful tool for the accurate prediction of RNA 3D structure. Availability and Implementation: The source package for BkTree is available at http://rna-informatics.uga.edu/index.php?f=software&p=BkTree. Contact:lding@uga.edu or cai@cs.uga.edu Supplementary information: Supplementary data are available at Bioinformatics online.


  • Open Access

    Big data - a 21st century science Maginot Line? No-boundary thinking: shifting from the big data paradigm

    by Xiuzhen Huang, Steven F Jennings, Barry Bruce, Alison Buchan, Liming Cai, Pengyin Chen, Carole L Cramer, Weihua Guan, Uwe Kk Hilgert, Hongmei Jiang, et al.

    Whether your interests lie in scientific arenas, the corporate world, or in government, you have certainly heard the praises of big data: Big data will give you new insights, allow you to become more efficient, and/or will solve your problems. While big data has had some outstanding successes, many are now beginning to see that it is not the Silver Bullet that it has been touted to be. Here our main concern is the overall impact of big data; the current manifestation of big data is constructing a Maginot Line in science in the 21st century. Big data is not “lots of data” as a phenomena anymore; The big data paradigm is putting the spirit of the Maginot Line into lots of data. Big data overall is disconnecting researchers and science challenges. We propose No-Boundary Thinking (NBT), applying no-boundary thinking in problem defining to address science challenges.


  • Open Access

    Ab initio Prediction of RNA Nucleotide Interactions with Backbone k-Tree Model

    by Liang Ding, Xingran Xue, Sal LaMarca, Mohammad Mohebbi, Abdul Samad, Russell L. Malmberg, Liming Cai

    Given the importance of non-coding RNAs to cellular regulatory functions and rapid growth of RNA transcripts, computational prediction of RNA tertiary structure remains highly demanded yet significantly challenging. Even for a short RNA sequence, the space of tertiary conformations is immense; existing methods to identify native-like conformations mostly resort to random sampling of conformations to gain computational feasibility. However native conformations may not be examined and prediction accuracy may be compromised due to sampling. In particular, the state-of-the-art methods have yet to deliver the desired prediction performance for RNAs of length beyond 50. This paper presents the work to tackle a key step in the RNA tertiary structure prediction problem, the prediction of the nucleotide interactions that constitute the desired tertiary structure. The research is established upon a novel graph model, called backbone k-tree, to markably constrain nucleotide interaction relationships in RNA tertiary structure. It is shown that the new model makes it possible to efficiently predict the optimal set of nucleotide interactions from the query sequence, including the interactions in all recently revealed families. Evident by the preliminary results, the new method can predict with a high accuracy the nucleotide interactions that constitute the tertiary structure of the query sequence, thus providing a viable solution towards ab initio prediction of RNA tertiary structure.

  • Open Access

    Polynomial kernels collapse the W-hierarchy

    by Liang Ding, Abdul Samad, Xingran Xue, Xiuzhen Huang, Liming Cai

    We prove that, for many parameterized problems in the class FPT, the existence of polynomial kernels implies the collapse of the W-hierarchy (i.e., W[P] = FPT). The collapsing results are also extended to assumed exponential kernels for problems in the class FPT. In particular, we establish a close relationship between polynomial (and exponential) kernelizability and the existence of sub-exponential time algorithms for a spectrum of circuit satisfiability problems in FPT. To the best of our knowledge, this is the first work that connects hardness for polynomial kernelizability of FPT problems to parameterized intractability. Our work also offers some new insights into the class FPT.

  • Open Access

    TRFolder-W: a web server for telomerase RNA structure prediction in yeast genomes

    by Dong Zhang, Xingran Xue, Russell L. Malmberg, Liming Cai

    Summary: TRFolder-W is a web server capable of predicting core structures of telomerase RNA (TR) in yeast genomes. TRFolder is a command-line Python toolkit for TR-specific structure prediction. We developed a web-version built on the django web framework, leveraging the work done previously, to include enhancements to increase flexibility of usage. To date, there are five core sub-structures commonly found in TR of fungal species, which are the template region, downstream pseudoknot, boundary element, core-closing stem and triple helix. The aim of TRFolder-W is to use the five core structures as fundamental units to predict potential TR genes for yeast, and to provide a user-friendly interface. Moreover, the application of TRFolder-W can be extended to predict the characteristic structure on species other than fungal species. Availability: The web server TRFolder-W is available at http://rna-informatics.uga.edu/?f=software&p=TRFolder-w. Contact: cai@cs.uga.edu Supplementary information:http://rna-informatics.uga.edu/?f=software&p=TRFolder-w-supplement.


  • Open Access

    Stable stem enabled Shannon entropies distinguish non-coding RNAs from random backgrounds

    by Yingfeng Wang, Amir Manzour, Pooya Shareghi, Timothy I Shaw, Ying-Wai Li, Russell L Malmberg, Liming Cai

    The computational identification of RNAs in genomic sequences requires the identification of signals of RNA sequences. Shannon base pairing entropy is an indicator for RNA secondary structure fold certainty in detection of structural, non-coding RNAs (ncRNAs). Under the Boltzmann ensemble of secondary structures, the probability of a base pair is estimated from its frequency across all the alternative equilibrium structures. However, such an entropy has yet to deliver the desired performance for distinguishing ncRNAs from random sequences. Developing novel methods to improve the entropy measure performance may result in more effective ncRNA gene finding based on structure detection.


  • Open Access

    Simultaneous prediction of RNA secondary structure and helix coaxial stacking

    by Pooya Shareghi, Yingfeng Wang, Russell Malmberg, Liming Cai

    RNA secondary structure plays a scaffolding role for RNA tertiary conformation. Accurate secondary structure prediction can not only identify double-stranded helices and single stranded-loops but also help provide information for potential tertiary interaction motifs critical to the 3D conformation. The average accuracy in ab initio prediction remains 70%; performance improvement has only been limited to short RNA sequences. The prediction of tertiary interaction motifs is difficult without multiple, related sequences that are usually not available. This paper presents research that aims to improve the secondary structure prediction performance and to develop a capability to predict coaxial stacking between helices. Coaxial stacking positions two helices on the same axis, a tertiary motif present in almost all junctions that account for a high percentage of RNA tertiary structures.


  • ANALYZING MODULAR RNA STRUCTURE REVEALS LOW GLOBAL STRUCTURAL ENTROPY IN MICRORNA SEQUENCE

    by Timothy I. Shaw, Amir Manzour, Yingfeng Wang, Russell L. Malmberg, Liming Cai

    Secondary structure remains the most exploitable feature for noncoding RNA (ncRNA) gene finding in genomes. However, methods based on secondary structure prediction may generate superfluous amount of candidates for validation and have yet to deliver the desired performance that can complement experimental efforts in ncRNA gene finding. This paper investigates a novel method, unpaired structural entropy (USE) as a measurement for the structure fold stability of ncRNAs. USE proves to be effective in identifying from the genome background a class of ncRNAs, such as precursor microRNAs (pre-miRNAs) that contains a long stem hairpin loop. USE correlates well and performs better than other measures on pre-miRNAs, including the previously formulated structural entropy. As an SVM classifier, USE outperforms existing pre-miRNA classifiers. A long stem hairpin loop is common for a number of other functional RNAs including introns splicing hairpins loops and intrinsic termination hairpin loops. We believe USE can be further applied in developing ab initio prediction programs for a larger class of ncRNAs.