Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Filtering Undesirable Flows in Networks Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

A New Approximation Algorithm for the Maximum Stacking Base Pairs Problem from RNA Secondary Structures Prediction

verfasst von : Aizhong Zhou, Haitao Jiang, Jiong Guo, Daming Zhu

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper investigates the problem of maximum stacking base pairs from RNA secondary structure prediction. The basic version of maximum stacking base pairs problem as: given an RNA sequence, to find a maximum number of base pairs where each base pair is involved in a stacking. Ieong et al. showed this problem to be NP-hard, where the candidate base pairs follow some biology principle and are given implicitly. In this paper, we study the version of this problem that the candidate base pairs are given explicitly as input, and present a new approximation algorithm for this problem by the local search method, improving the approximation factor from 5/2 to 7/3. The time complexity is within \(O(n^{14})\), since we adopt 1-substitution and special 2-substitutions in the local improvement steps.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel On the Profit-Maximizing for Transaction Platforms in Crowd Sensing
Nächstes Kapitel Approximation Algorithms for the Generalized Stacker Crane Problem
Literatur
1.
Tinoco Jr., I., Bustamante, C.: How RNA folds. J. Mol. Biol. 293, 271–281 (1999)CrossRef
2.
Nussinov, R., Pieczenik, G., Griggs, J.R., Kleitman, D.J.: Algorithms for loop matchings. SIAM J. Appl. Math. 35(1), 68–82 (1978)CrossRefMATHMathSciNet
3.
Nussinov, R., Jacobson, A.B.: Fast algorithm for predicting the secondary structure of single-stranded RNA. Proc. Natl. Acad. Sci. USA 77, 6309–6313 (1980)CrossRef
4.
Zuker, M., Stiegler, P.: Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 9, 133–148 (1981)CrossRef
5.
Zuker, M., Sankoff, D.: RNA secondary structures and their prediction. Bull. Math. Biol. 46, 591–621 (1984)CrossRefMATH
6.
Sankoff, D.: Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J. Appl. Math. 45, 810–825 (1985)CrossRefMATHMathSciNet
7.
Lyngsø, R.B., Zuker, M., Pedersen, C.N.S.: Fast evaluation of interval loops in RNA secondary structure prediction. Bioinformatics 15, 440–445 (1999)CrossRef
8.
Lyngsø, R.B., Pedersen, C.N.S.: RNA pseudoknot prediction in energy based models. J. Comput. Biol. 7(3/4), 409–428 (2000)CrossRef
9.
Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Appl. Math. 104(1–3), 45–62 (2000)CrossRefMATHMathSciNet
10.
Rivas, E., Eddy, S.R.: A dynamic programming algorithm for RNA structure prediction including pseudoknots. J. Mol. Biol. 285(5), 2053–2068 (1999)CrossRef
11.
Uemura, Y., Hasegawa, A., Kobayashi, S., Yokomori, T.: Tree adjoining grammars for RNA structure prediction. Theoret. Comput. Sci. 210(2), 277–303 (1999)CrossRefMATHMathSciNet
12.
Tinoco Jr., I., Borer, P.N., Dengler, B., Levine, M.D., Uhlenbeck, O.C., Crothers, D.M., Gralla, J.: Improved estimation of secondary structure in ribonucleic acids. Nature New Biol. 246, 40–42 (1973)CrossRef
13.
Ieong, S., Kao, M.-Y., Lam, T.-W., Sung, W.-K., Yiu, S.-M.: Predicting RNA secondary structure with arbitrary pseudoknots by maximizing the number of stacking pairs. J. Comput. Biol. 10, 981–995 (2003)CrossRef
14.
15.
Jiang, M.: Approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. IEEE/ACM Trans. Comput. Biol. Bioinform. 7(2), 323–332 (2010)CrossRef
16.
Berman, P.: A \(d\)/2 approximation for maximum weight independent set in \(d\)-Claw Free Graphs. Nordic J. Comput. 7, 178–184 (2000)MATHMathSciNet
17.
Metadaten
Titel
A New Approximation Algorithm for the Maximum Stacking Base Pairs Problem from RNA Secondary Structures Prediction
verfasst von
Aizhong Zhou
Haitao Jiang
Jiong Guo
Daming Zhu
Copyright-Jahr
2017
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-71149-2

Electronic ISBN: 978-3-319-71150-8

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-71150-8_7