Multiple RNA Interaction - Formulations, Approximations, and Heuristics

Saad Mneimneh, Syed Ali Ahmed, Nancy L. Greenbaum

2013

Abstract

The interaction of two RNA molecules involves a complex interplay between folding and binding that warranted recent developments in RNA-RNA interaction algorithms. However, biological mechanisms in which more than two RNAs take part in an interaction exist. Therefore, we formulate multiple RNA interaction as a computational problem, which not surprisingly turns out to be NP-complete. Our experiments with approximation algorithms and heuristics for the problem suggest that this formulation is indeed useful to determine interaction patterns of multiple RNAs when information about which RNAs interact is not necessarily available (as opposed to the case of two RNAs where one must interact with the other), and because the resulting RNA structure often cannot be predicated by existing algorithms when RNAs are simply handled in pairs.

Download


Paper Citation


in Harvard Style

Mneimneh S., Ali Ahmed S. and L. Greenbaum N. (2013). Multiple RNA Interaction - Formulations, Approximations, and Heuristics . In Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms - Volume 1: BIOINFORMATICS, (BIOSTEC 2013) ISBN 978-989-8565-35-8, pages 242-249. DOI: 10.5220/0004341402420249

in Bibtex Style

@conference{bioinformatics13,
author={Saad Mneimneh and Syed Ali Ahmed and Nancy L. Greenbaum},
title={Multiple RNA Interaction - Formulations, Approximations, and Heuristics},
booktitle={Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms - Volume 1: BIOINFORMATICS, (BIOSTEC 2013)},
year={2013},
pages={242-249},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004341402420249},
isbn={978-989-8565-35-8},
}


in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms - Volume 1: BIOINFORMATICS, (BIOSTEC 2013)
TI - Multiple RNA Interaction - Formulations, Approximations, and Heuristics
SN - 978-989-8565-35-8
AU - Mneimneh S.
AU - Ali Ahmed S.
AU - L. Greenbaum N.
PY - 2013
SP - 242
EP - 249
DO - 10.5220/0004341402420249