Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
SPARSE: Quadratic Time Simultaneous Alignment and Folding of RNAs without Sequence-Based Heuristics
verfasst von : Sebastian Will, Christina Schmiedl, Milad Miladi, Mathias Möhl, Rolf Backofen
Erschienen in: Research in Computational Molecular Biology
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Motivation:
There is increasing evidence of pervasive transcription, resulting in hundreds of thousands of ncRNAs of unknown function. Standard computational analysis tasks for inferring functional annotations like clustering require fast and accurate RNA comparisons based on sequence and structure similarity. The gold standard for the latter is Sankoff’s algorithm [3], which simultaneously aligns and folds RNAs. Because of its extreme time complexity of
O
(
n
6
), numerous faster “Sankoff-style” approaches have been suggested. Several such approaches introduce heuristics based on sequence alignment, which compromises the alignment quality for RNAs with sequence identities below 60% [1]. Avoiding such heuristics, as e.g. in LocARNA [4], has been assumed to prohibit time complexities better than
O
(
n
4
), which strongly limits large-scale applications.