Bakgrund: Det allmänna problemet med RNA sekundär struktur förutsägelse under den allmänt använda termodynamiska modellen är känd för att vara NP-komplett när de strukturer som anses innehålla godtyckliga pseudoknots. För begränsade klasser av pseudoknots, flera polynom tid algoritmer har utformats, där O(n 6 )tid och O(n 4 ) utrymme algoritm av Rivas och Eddy är för närvarande det bästa tillgängliga programmet.
Reeder och Giegerich REF förbättrade komplexiteten i algoritmen, nå O(n 4) utrymme och O(n 2 ) tid, med hjälp av Minimal Free Energy (MFE) modellen.
Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics
{'venue': 'BMC Bioinformatics', 'journal': 'BMC Bioinformatics', 'mag_field_of_study': ['Computer Science', 'Medicine']}