Bi-objective integer programming for RNA secondary structure prediction with pseudoknots
Abstract Background RNA structure prediction is an important field in bioinformatics, and numerous methods and tools have been proposed. Pseudoknots are specific motifs of RNA secondary structures that are difficult to predict. Almost all existing methods are based on a single model and return one s...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2018-01-01
|
| Series: | BMC Bioinformatics |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s12859-018-2007-7 |
| _version_ | 1818898329990332416 |
|---|---|
| author | Audrey Legendre Eric Angel Fariza Tahi |
| author_facet | Audrey Legendre Eric Angel Fariza Tahi |
| author_sort | Audrey Legendre |
| collection | DOAJ |
| description | Abstract Background RNA structure prediction is an important field in bioinformatics, and numerous methods and tools have been proposed. Pseudoknots are specific motifs of RNA secondary structures that are difficult to predict. Almost all existing methods are based on a single model and return one solution, often missing the real structure. An alternative approach would be to combine different models and return a (small) set of solutions, maximizing its quality and diversity in order to increase the probability that it contains the real structure. Results We propose here an original method for predicting RNA secondary structures with pseudoknots, based on integer programming. We developed a generic bi-objective integer programming algorithm allowing to return optimal and sub-optimal solutions optimizing simultaneously two models. This algorithm was then applied to the combination of two known models of RNA secondary structure prediction, namely MEA and MFE. The resulting tool, called BiokoP, is compared with the other methods in the literature. The results show that the best solution (structure with the highest F1-score) is, in most cases, given by BiokoP. Moreover, the results of BiokoP are homogeneous, regardless of the pseudoknot type or the presence or not of pseudoknots. Indeed, the F1-scores are always higher than 70% for any number of solutions returned. Conclusion The results obtained by BiokoP show that combining the MEA and the MFE models, as well as returning several optimal and several sub-optimal solutions, allow to improve the prediction of secondary structures. One perspective of our work is to combine better mono-criterion models, in particular to combine a model based on the comparative approach with the MEA and the MFE models. This leads to develop in the future a new multi-objective algorithm to combine more than two models. BiokoP is available on the EvryRNA platform: https://EvryRNA.ibisc.univ-evry.fr . |
| first_indexed | 2024-12-19T19:30:21Z |
| format | Article |
| id | doaj.art-040f82c043754edd963515b4312a3b09 |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-12-19T19:30:21Z |
| publishDate | 2018-01-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-040f82c043754edd963515b4312a3b092022-12-21T20:08:36ZengBMCBMC Bioinformatics1471-21052018-01-0119111510.1186/s12859-018-2007-7Bi-objective integer programming for RNA secondary structure prediction with pseudoknotsAudrey Legendre0Eric Angel1Fariza Tahi2IBISC, Univ Evry, Université Paris-SaclayIBISC, Univ Evry, Université Paris-SaclayIBISC, Univ Evry, Université Paris-SaclayAbstract Background RNA structure prediction is an important field in bioinformatics, and numerous methods and tools have been proposed. Pseudoknots are specific motifs of RNA secondary structures that are difficult to predict. Almost all existing methods are based on a single model and return one solution, often missing the real structure. An alternative approach would be to combine different models and return a (small) set of solutions, maximizing its quality and diversity in order to increase the probability that it contains the real structure. Results We propose here an original method for predicting RNA secondary structures with pseudoknots, based on integer programming. We developed a generic bi-objective integer programming algorithm allowing to return optimal and sub-optimal solutions optimizing simultaneously two models. This algorithm was then applied to the combination of two known models of RNA secondary structure prediction, namely MEA and MFE. The resulting tool, called BiokoP, is compared with the other methods in the literature. The results show that the best solution (structure with the highest F1-score) is, in most cases, given by BiokoP. Moreover, the results of BiokoP are homogeneous, regardless of the pseudoknot type or the presence or not of pseudoknots. Indeed, the F1-scores are always higher than 70% for any number of solutions returned. Conclusion The results obtained by BiokoP show that combining the MEA and the MFE models, as well as returning several optimal and several sub-optimal solutions, allow to improve the prediction of secondary structures. One perspective of our work is to combine better mono-criterion models, in particular to combine a model based on the comparative approach with the MEA and the MFE models. This leads to develop in the future a new multi-objective algorithm to combine more than two models. BiokoP is available on the EvryRNA platform: https://EvryRNA.ibisc.univ-evry.fr .http://link.springer.com/article/10.1186/s12859-018-2007-7RNASecondary structurePseudoknotInteger programmingBi-objectiveOptimal solutions |
| spellingShingle | Audrey Legendre Eric Angel Fariza Tahi Bi-objective integer programming for RNA secondary structure prediction with pseudoknots BMC Bioinformatics RNA Secondary structure Pseudoknot Integer programming Bi-objective Optimal solutions |
| title | Bi-objective integer programming for RNA secondary structure prediction with pseudoknots |
| title_full | Bi-objective integer programming for RNA secondary structure prediction with pseudoknots |
| title_fullStr | Bi-objective integer programming for RNA secondary structure prediction with pseudoknots |
| title_full_unstemmed | Bi-objective integer programming for RNA secondary structure prediction with pseudoknots |
| title_short | Bi-objective integer programming for RNA secondary structure prediction with pseudoknots |
| title_sort | bi objective integer programming for rna secondary structure prediction with pseudoknots |
| topic | RNA Secondary structure Pseudoknot Integer programming Bi-objective Optimal solutions |
| url | http://link.springer.com/article/10.1186/s12859-018-2007-7 |
| work_keys_str_mv | AT audreylegendre biobjectiveintegerprogrammingforrnasecondarystructurepredictionwithpseudoknots AT ericangel biobjectiveintegerprogrammingforrnasecondarystructurepredictionwithpseudoknots AT farizatahi biobjectiveintegerprogrammingforrnasecondarystructurepredictionwithpseudoknots |