STRUCTURE PREDICTION OF SIMPLE NON-STANDARD PSEUDOKNOT

Thomas K. F. Wong, S. M. Yiu

2010

Abstract

The secondary structure of an RNA molecule is known to be critical in its biological function. However, the problem of predicting the secondary structure of an RNA molecule based on its primary sequence is computationally difficult in the presence of pseudoknots. In general, the problem is NP-hard. Most of the existing algorithms aim at restricted classes of pseudoknots. In this paper, we consider a new class of pseudoknot structures, called simple non-standard pseudoknot, which can cover more complicated secondary structures found in existing databases. None of the previous algorithms can handle this class of pseudoknots. Only two of them, which run in O(m6) and O(m5) time where m is the length of the given RNA sequence, can handle certain cases in this new class. On the other hand, we provide a prediction algorithm that runs in O(m4) time for simple non-standard pseudoknots of degree 4 which already covers all known secondary structures of RNAs in this class.

Paper Citation

in Harvard Style

K. F. Wong T. and M. Yiu S. (2010). STRUCTURE PREDICTION OF SIMPLE NON-STANDARD PSEUDOKNOT . In Proceedings of the First International Conference on Bioinformatics - Volume 1: BIOINFORMATICS, (BIOSTEC 2010) ISBN 978-989-674-019-1, pages 33-38. DOI: 10.5220/0002718000330038

in Bibtex Style

@conference{bioinformatics10,
author={Thomas K. F. Wong and S. M. Yiu},
title={STRUCTURE PREDICTION OF SIMPLE NON-STANDARD PSEUDOKNOT},
booktitle={Proceedings of the First International Conference on Bioinformatics - Volume 1: BIOINFORMATICS, (BIOSTEC 2010)},
year={2010},
pages={33-38},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002718000330038},
isbn={978-989-674-019-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Bioinformatics - Volume 1: BIOINFORMATICS, (BIOSTEC 2010)
TI - STRUCTURE PREDICTION OF SIMPLE NON-STANDARD PSEUDOKNOT
SN - 978-989-674-019-1
AU - K. F. Wong T.
AU - M. Yiu S.
PY - 2010
SP - 33
EP - 38
DO - 10.5220/0002718000330038