Christian Reidys

Prof. Dr. Christian Reidys

Department of Mathematics, University of Virginia, Director at the Biocomplexity Institute of The University of Virginia, Charlottesville, VA, USA

Research Focus & Metrics

Academic Career Length

31Years (1996-Present)

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

Representative Publications

View All Publications
17 February 2011 in Bioinformatics
Verified
Journal Article
Open access
PDF file
Christian ReidysChristian Reidys
Christian Reidys
WHWenda Huang
Wenda Huang
JAJørgen E. Andersen
Jørgen E. Andersen
RPRobert C. Penner
Robert C. Penner
Peter F. StadlerPeter F. Stadler
Peter F. Stadler
MNMarkus E. Nebel
Markus E. Nebel
Motivation: Several dynamic programming algorithms for predicting RNA structures with pseudoknots have been proposed that differ dramatically from one another in the classes of structures considered. Results: Here, we use the natural topological classification of RNA structures in terms of irreducible components that are embeddable in the surfaces of fixed genus. We add to the conventional secondary structures four building blocks of genus one in order to construct certain structures of arbitrarily high genus. A corresponding unambiguous multiple context-free grammar provides an efficient dynamic programming approach for energy minimization, partition function and stochastic sampling. It admits a topology-dependent parametrization of pseudoknot penalties that increases the sensitivity and positive predictive value of predicted base pairs by 10–20% compared with earlier approaches. More general models based on building blocks of higher genus are also discussed. Availability: The source code of gfold is freely available at http://www.combinatorics.cn/cbpc/gfold.tar.gz. Contact:duck@santafe.edu Supplementary information: Supplementary data are available at Bioinformatics online.

11 August 2009 in Bioinformatics
Verified
Journal Article
Open access
PDF file
WHWenda Huang
Wenda Huang
JQJing Qin
Jing Qin
Christian ReidysChristian Reidys
Christian Reidys
Peter F. StadlerPeter F. Stadler
Peter F. Stadler
Motivation: The RNA–RNA interaction problem (RIP) consists in finding the energetically optimal structure of two RNA molecules that bind to each other. The standard model allows secondary structures in both partners as well as additional base pairs between the two RNAs subject to certain restrictions that ensure that RIP is solvabale by a polynomial time dynamic programming algorithm. RNA–RNA binding, like RNA folding, is typically not dominated by the ground state structure. Instead, a large ensemble of alternative structures contributes to the interaction thermodynamics. Results: We present here an O(N6) time and O(N4) dynamics programming algorithm for computing the full partition function for RIP which is based on the combinatorial notion of ‘tight structures’. Albeit equivalent to recent work by H. Chitsaz and collaborators, our approach in addition provides a full-fledged computation of the base pairing probabilities, which relies on the notion of a decomposition tree for joint structures. In practise, our implementation is efficient enough to investigate, for instance, the interactions of small bacterial RNAs and their target mRNAs. Availability: The program rip is implemented in C. The source code is available for download from http://www.combinatorics.cn/cbpc/rip.html and http://www.bioinf.uni-leipzig.de/Software/rip.html. Contact:duck@santafe.edu Supplementary information: Supplementary data are available at Bioinformatics online.

2 October 2012 in Journal of Mathematical Biology
Verified
Journal Article
Closed access
PDF file
JAJ.E. Andersen
J.E. Andersen
RPR.C. Penner
R.C. Penner
Christian ReidysChristian Reidys
Christian Reidys
MWM.S. Waterman
M.S. Waterman

13 November 2009 in Bioinformatics
Verified
Journal Article
Open access
PDF file
WHWenda Huang
Wenda Huang
JQJing Qin
Jing Qin
Christian ReidysChristian Reidys
Christian Reidys
Peter F. StadlerPeter F. Stadler
Peter F. Stadler
Motivation: It has been proven that the accessibility of the target sites has a critical influence on RNA–RNA binding, in general and the specificity and efficiency of miRNAs and siRNAs, in particular. Recently, O(N6) time and O(N4) space dynamic programming (DP) algorithms have become available that compute the partition function of RNA–RNA interaction complexes, thereby providing detailed insights into their thermodynamic properties. Results: Modifications to the grammars underlying earlier approaches enables the calculation of interaction probabilities for any given interval on the target RNA. The computation of the ‘hybrid probabilities’ is complemented by a stochastic sampling algorithm that produces a Boltzmann weighted ensemble of RNA–RNA interaction structures. The sampling of k structures requires only negligible additional memory resources and runs in O(k·N3). Availability: The algorithms described here are implemented in C as part of the rip package. The source code of rip2 can be downloaded from http://www.combinatorics.cn/cbpc/rip.html and http://www.bioinf.uni-leipzig.de/Software/rip.html. Contact:duck@santafe.edu Supplementary information: Supplementary data are available at Bioinformatics online.

5 December 2010 in Bioinformatics
Verified
Journal Article
Open access
PDF file
ALAndrew X. Li
Andrew X. Li
MMManja Marz
Manja Marz
JQJing Qin
Jing Qin
Christian ReidysChristian Reidys
Christian Reidys
Motivation: Many computerized methods for RNA–RNA interaction structure prediction have been developed. Recently, O(N6) time and O(N4) space dynamic programming algorithms have become available that compute the partition function of RNA–RNA interaction complexes. However, few of these methods incorporate the knowledge concerning related sequences, thus relevant evolutionary information is often neglected from the structure determination. Therefore, it is of considerable practical interest to introduce a method taking into consideration both: thermodynamic stability as well as sequence/structure covariation. Results: We present the a priori folding algorithm ripalign, whose input consists of two (given) multiple sequence alignments (MSA). ripalign outputs (i) the partition function, (ii) base pairing probabilities, (iii) hybrid probabilities and (iv) a set of Boltzmann-sampled suboptimal structures consisting of canonical joint structures that are compatible to the alignments. Compared to the single sequence-pair folding algorithm rip, ripalign requires negligible additional memory resource but offers much better sensitivity and specificity, once alignments of suitable quality are given. ripalign additionally allows to incorporate structure constraints as input parameters. Availability: The algorithm described here is implemented in C as part of the rip package. The supplemental material, source code and input/output files can freely be downloaded from http://www.combinatorics.cn/cbpc/ripalign.html. Contact:duck@santafe.edu Supplementary information: Supplementary data are available at Bioinformatics online.

1 July 2012 in Journal of Computational Biology
Verified
Journal Article
Closed access
JAJørgen E. Andersen
Jørgen E. Andersen
WHWenda Huang
Wenda Huang
RPRobert C. Penner
Robert C. Penner
Christian ReidysChristian Reidys
Christian Reidys
The topological filtration of interacting RNA complexes is studied, and the role is analyzed of certain diagrams called irreducible shadows, which form suitable building blocks for more general structures. We prove that, for two interacting RNAs, called interaction structures, there exist for fixed genus only finitely many irreducible shadows. This implies that, for fixed genus, there are only finitely many classes of interaction structures. In particular, the simplest case of genus zero already provides the formalism for certain types of structures that occur in nature and are not covered by other filtrations. This case of genus zero interaction structures is already of practical interest, is studied here in detail, and is found to be expressed by a multiple context-free grammar that extends the usual one for RNA secondary structures. We show that, in O(n6) time and O(n4) space complexity, this grammar for genus zero interaction structures provides not only minimum free energy solutions but also the complete partition function and base pairing probabilities.