Liming Cai

Liming Cai


Research Focus & Metrics

Academic Career Length

24Years (2003-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
3 July 2003 in Bioinformatics
Verified
Journal Article
Open access
PDF file
LCLiming Cai
Liming Cai
RMRussell L. Malmberg
Russell L. Malmberg
YWYunzhou Wu
Yunzhou Wu
Motivation: Modeling RNA pseudoknotted structures remains challenging. Methods have previously been developed to model RNA stem-loops successfully using stochastic context-free grammars (SCFG) adapted from computational linguistics; however, the additional complexity of pseudoknots has made modeling them more difficult. Formally a context-sensitive grammar is required, which would impose a large increase in complexity. Results: We introduce a new grammar modeling approach for RNA pseudoknotted structures based on parallel communicating grammar systems (PCGS). Our new approach can specify pseudoknotted structures, while avoiding context-sensitive rules, using a single CFG synchronized with a number of regular grammars. Technically, the stochastic version of the grammar model can be as simple as an SCFG. As with SCFG, the new approach permits automatic generation of a single-RNA structure prediction algorithm for each specified pseudoknotted structure model. This approach also makes it possible to develop full probabilistic models of pseudoknotted structures to allow the prediction of consensus structures by comparative analysis and structural homology recognition in database searches. Availability: Prototypes for the automated pseudoknot prediction algorithm are available upon request. Contact: cai@cs.uga.edu; russell@plantbio.uga.edu *To whom correspondence should be addressed.

12 April 2012 in BMC Bioinformatics
Verified
Journal Article
Open access
PDF file
YWYingfeng Wang
Yingfeng Wang
AMAmir Manzour
Amir Manzour
PSPooya Shareghi
Pooya Shareghi
TSTimothy I Shaw
Timothy I Shaw
YLYing-Wai Li
Ying-Wai Li
LCLiming Cai
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.

15 August 2008 in Algorithmica
Verified
Journal Article
Closed access
PDF file
LCLiming Cai
Liming Cai
XHXiuzhen Huang
Xiuzhen Huang

7 August 2008 in Bioinformatics
Verified
Journal Article
Open access
PDF file
ZHZhibin Huang
Zhibin Huang
YWYong Wu
Yong Wu
JRJoseph Robertson
Joseph Robertson
LFLiang Feng
Liang Feng
RMRussell L. Malmberg
Russell L. Malmberg
LCLiming Cai
Liming Cai
Motivation: Searching genomes for non-coding RNAs (ncRNAs) by their secondary structure has become an important goal for bioinformatics. For pseudoknot-free structures, ncRNA search can be effective based on the covariance model and CYK-type dynamic programming. However, the computational difficulty in aligning an RNA sequence to a pseudoknot has prohibited fast and accurate search of arbitrary RNA structures. Our previous work introduced a graph model for RNA pseudoknots and proposed to solve the structure–sequence alignment by graph optimization. Given k candidate regions in the target sequence for each of the n stems in the structure, we could compute a best alignment in time O(ktn) based upon a tree width t decomposition of the structure graph. However, to implement this method to programs that can routinely perform fast yet accurate RNA pseudoknot searches, we need novel heuristics to ensure that, without degrading the accuracy, only a small number of stem candidates need to be examined and a tree decomposition of a small tree width can always be found for the structure graph. Results: The current work builds on the previous one with newly developed preprocessing algorithms to reduce the values for parameters k and t and to implement the search method into a practical program, called RNATOPS, for RNA pseudoknot search. In particular, we introduce techniques, based on probabilistic profiling and distance penalty functions, which can identify for every stem just a small number k (e.g. k ≤ 10) of plausible regions in the target sequence to which the stem needs to align. We also devised a specialized tree decomposition algorithm that can yield tree decomposition of small tree width t (e.g. t ≤ 4) for almost all RNA structure graphs. Our experiments show that with RNATOPS it is possible to routinely search prokaryotic and eukaryotic genomes for specific RNA structures of medium to large sizes, including pseudoknots, with high sensitivity and high specificity, and in a reasonable amount of time. Availability: The source code in C++ for RNATOPS is available at www.uga.edu/RNA-Informatics/software/rnatops/ Contact:cai@cs.uga.edu Supplementary information: The online Supplementary Material contains all illustrative figures and tables referenced by this article.

29 September 2007 in Journal of Mathematical Biology
Verified
Journal Article
Closed access
PDF file
JZJizhen Zhao
Jizhen Zhao
RMRussell L. Malmberg
Russell L. Malmberg
LCLiming Cai
Liming Cai

6 February 2015 in BioData Mining
Verified
Journal Article
Open access
PDF file
XHXiuzhen Huang
Xiuzhen Huang
SJSteven F Jennings
Steven F Jennings
BBBarry Bruce
Barry Bruce
ABAlison Buchan
Alison Buchan
LCLiming Cai
Liming Cai
JMJason H. Moore
Jason H. Moore
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.