Cargando…

Fast Pairwise Structural RNA Alignments by Pruning of the Dynamical Programming Matrix

It has become clear that noncoding RNAs (ncRNA) play important roles in cells, and emerging studies indicate that there might be a large number of unknown ncRNAs in mammalian genomes. There exist computational methods that can be used to search for ncRNAs by comparing sequences from different genome...

Descripción completa

Detalles Bibliográficos
Autores principales: Havgaard, Jakob H, Torarinsson, Elfar, Gorodkin, Jan
Formato: Texto
Lenguaje:English
Publicado: Public Library of Science 2007
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2014794/
https://www.ncbi.nlm.nih.gov/pubmed/17937495
http://dx.doi.org/10.1371/journal.pcbi.0030193
_version_ 1782136568938496000
author Havgaard, Jakob H
Torarinsson, Elfar
Gorodkin, Jan
author_facet Havgaard, Jakob H
Torarinsson, Elfar
Gorodkin, Jan
author_sort Havgaard, Jakob H
collection PubMed
description It has become clear that noncoding RNAs (ncRNA) play important roles in cells, and emerging studies indicate that there might be a large number of unknown ncRNAs in mammalian genomes. There exist computational methods that can be used to search for ncRNAs by comparing sequences from different genomes. One main problem with these methods is their computational complexity, and heuristics are therefore employed. Two heuristics are currently very popular: pre-folding and pre-aligning. However, these heuristics are not ideal, as pre-aligning is dependent on sequence similarity that may not be present and pre-folding ignores the comparative information. Here, pruning of the dynamical programming matrix is presented as an alternative novel heuristic constraint. All subalignments that do not exceed a length-dependent minimum score are discarded as the matrix is filled out, thus giving the advantage of providing the constraints dynamically. This has been included in a new implementation of the FOLDALIGN algorithm for pairwise local or global structural alignment of RNA sequences. It is shown that time and memory requirements are dramatically lowered while overall performance is maintained. Furthermore, a new divide and conquer method is introduced to limit the memory requirement during global alignment and backtrack of local alignment. All branch points in the computed RNA structure are found and used to divide the structure into smaller unbranched segments. Each segment is then realigned and backtracked in a normal fashion. Finally, the FOLDALIGN algorithm has also been updated with a better memory implementation and an improved energy model. With these improvements in the algorithm, the FOLDALIGN software package provides the molecular biologist with an efficient and user-friendly tool for searching for new ncRNAs. The software package is available for download at http://foldalign.ku.dk.
format Text
id pubmed-2014794
institution National Center for Biotechnology Information
language English
publishDate 2007
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-20147942007-10-25 Fast Pairwise Structural RNA Alignments by Pruning of the Dynamical Programming Matrix Havgaard, Jakob H Torarinsson, Elfar Gorodkin, Jan PLoS Comput Biol Research Article It has become clear that noncoding RNAs (ncRNA) play important roles in cells, and emerging studies indicate that there might be a large number of unknown ncRNAs in mammalian genomes. There exist computational methods that can be used to search for ncRNAs by comparing sequences from different genomes. One main problem with these methods is their computational complexity, and heuristics are therefore employed. Two heuristics are currently very popular: pre-folding and pre-aligning. However, these heuristics are not ideal, as pre-aligning is dependent on sequence similarity that may not be present and pre-folding ignores the comparative information. Here, pruning of the dynamical programming matrix is presented as an alternative novel heuristic constraint. All subalignments that do not exceed a length-dependent minimum score are discarded as the matrix is filled out, thus giving the advantage of providing the constraints dynamically. This has been included in a new implementation of the FOLDALIGN algorithm for pairwise local or global structural alignment of RNA sequences. It is shown that time and memory requirements are dramatically lowered while overall performance is maintained. Furthermore, a new divide and conquer method is introduced to limit the memory requirement during global alignment and backtrack of local alignment. All branch points in the computed RNA structure are found and used to divide the structure into smaller unbranched segments. Each segment is then realigned and backtracked in a normal fashion. Finally, the FOLDALIGN algorithm has also been updated with a better memory implementation and an improved energy model. With these improvements in the algorithm, the FOLDALIGN software package provides the molecular biologist with an efficient and user-friendly tool for searching for new ncRNAs. The software package is available for download at http://foldalign.ku.dk. Public Library of Science 2007-10 2007-10-12 /pmc/articles/PMC2014794/ /pubmed/17937495 http://dx.doi.org/10.1371/journal.pcbi.0030193 Text en © 2007 Havgaard et al. http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited.
spellingShingle Research Article
Havgaard, Jakob H
Torarinsson, Elfar
Gorodkin, Jan
Fast Pairwise Structural RNA Alignments by Pruning of the Dynamical Programming Matrix
title Fast Pairwise Structural RNA Alignments by Pruning of the Dynamical Programming Matrix
title_full Fast Pairwise Structural RNA Alignments by Pruning of the Dynamical Programming Matrix
title_fullStr Fast Pairwise Structural RNA Alignments by Pruning of the Dynamical Programming Matrix
title_full_unstemmed Fast Pairwise Structural RNA Alignments by Pruning of the Dynamical Programming Matrix
title_short Fast Pairwise Structural RNA Alignments by Pruning of the Dynamical Programming Matrix
title_sort fast pairwise structural rna alignments by pruning of the dynamical programming matrix
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2014794/
https://www.ncbi.nlm.nih.gov/pubmed/17937495
http://dx.doi.org/10.1371/journal.pcbi.0030193
work_keys_str_mv AT havgaardjakobh fastpairwisestructuralrnaalignmentsbypruningofthedynamicalprogrammingmatrix
AT torarinssonelfar fastpairwisestructuralrnaalignmentsbypruningofthedynamicalprogrammingmatrix
AT gorodkinjan fastpairwisestructuralrnaalignmentsbypruningofthedynamicalprogrammingmatrix