Browse
Submit Data
Databases
API
Help

Dataset Information

41 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Local structural alignment of RNA with affine gap model.

ABSTRACT:

Background

Predicting new non-coding RNAs (ncRNAs) of a family can be done by aligning the potential candidate with a member of the family with known sequence and secondary structure. Existing tools either only consider the sequence similarity or cannot handle local alignment with gaps.

Results

In this paper, we consider the problem of finding the optimal local structural alignment between a query RNA sequence (with known secondary structure) and a target sequence (with unknown secondary structure) with the affine gap penalty model. We provide the algorithm to solve the problem.

Conclusions

Based on an experiment, we show that there are ncRNA families in which considering local structural alignment with gap penalty model can identify real hits more effectively than using global alignment or local alignment without gap penalty model.

SUBMITTER: King-Fung Wong T

PROVIDER: S-EPMC3090760 | biostudies-literature | 2011 May

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Local structural alignment of RNA with affine gap model.

King-Fung Wong Thomas T Wing-Yan Cheung Brenda B Lam Tak-Wah TW Yiu Siu-Ming SM

BMC proceedings 20110528

<h4>Background</h4>Predicting new non-coding RNAs (ncRNAs) of a family can be done by aligning the potential candidate with a member of the family with known sequence and secondary structure. Existing tools either only consider the sequence similarity or cannot handle local alignment with gaps.<h4>Results</h4>In this paper, we consider the problem of finding the optimal local structural alignment between a query RNA sequence (with known secondary structure) and a target sequence (with unknown se ...[more]

PMID: 21554760

Similar Datasets

Optimal gap-affine alignment in O(s) space.

Project description:MotivationPairwise sequence alignment remains a fundamental problem in computational biology and bioinformatics. Recent advances in genomics and sequencing technologies demand faster and scalable algorithms that can cope with the ever-increasing sequence lengths. Classical pairwise alignment algorithms based on dynamic programming are strongly limited by quadratic requirements in time and memory. The recently proposed wavefront alignment algorithm (WFA) introduced an efficient algorithm to perform exact gap-affine alignment in O(ns) time, where s is the optimal score and n is the sequence length. Notwithstanding these bounds, WFA's O(s2) memory requirements become computationally impractical for genome-scale alignments, leading to a need for further improvement.ResultsIn this article, we present the bidirectional WFA algorithm, the first gap-affine algorithm capable of computing optimal alignments in O(s) memory while retaining WFA's time complexity of O(ns). As a result, this work improves the lowest known memory bound O(n) to compute gap-affine alignments. In practice, our implementation never requires more than a few hundred MBs aligning noisy Oxford Nanopore Technologies reads up to 1 Mbp long while maintaining competitive execution times.Availability and implementationAll code is publicly available at https://github.com/smarco/BiWFA-paper.Supplementary informationSupplementary data are available at Bioinformatics online.

| S-EPMC9940620 | biostudies-literature

Fast gap-affine pairwise alignment using the wavefront algorithm.

Project description:MotivationPairwise alignment of sequences is a fundamental method in modern molecular biology, implemented within multiple bioinformatics tools and libraries. Current advances in sequencing technologies press for the development of faster pairwise alignment algorithms that can scale with increasing read lengths and production yields.ResultsIn this article, we present the wavefront alignment algorithm (WFA), an exact gap-affine algorithm that takes advantage of homologous regions between the sequences to accelerate the alignment process. As opposed to traditional dynamic programming algorithms that run in quadratic time, the WFA runs in time O(ns), proportional to the read length n and the alignment score s, using O(s2) memory. Furthermore, our algorithm exhibits simple data dependencies that can be easily vectorized, even by the automatic features of modern compilers, for different architectures, without the need to adapt the code. We evaluate the performance of our algorithm, together with other state-of-the-art implementations. As a result, we demonstrate that the WFA runs 20-300× faster than other methods aligning short Illumina-like sequences, and 10-100× faster using long noisy reads like those produced by Oxford Nanopore Technologies.Availability and implementationThe WFA algorithm is implemented within the wavefront-aligner library, and it is publicly available at https://github.com/smarco/WFA.

| S-EPMC8355039 | biostudies-literature

WFA-GPU: gap-affine pairwise read-alignment using GPUs.

Project description:MotivationAdvances in genomics and sequencing technologies demand faster and more scalable analysis methods that can process longer sequences with higher accuracy. However, classical pairwise alignment methods, based on dynamic programming (DP), impose impractical computational requirements to align long and noisy sequences like those produced by PacBio and Nanopore technologies. The recently proposed wavefront alignment (WFA) algorithm paves the way for more efficient alignment tools, improving time and memory complexity over previous methods. However, high-performance computing (HPC) platforms require efficient parallel algorithms and tools to exploit the computing resources available on modern accelerator-based architectures.ResultsThis paper presents WFA-GPU, a GPU (graphics processing unit)-accelerated tool to compute exact gap-affine alignments based on the WFA algorithm. We present the algorithmic adaptations and performance optimizations that allow exploiting the massively parallel capabilities of modern GPU devices to accelerate the alignment computations. In particular, we propose a CPU-GPU co-design capable of performing inter-sequence and intra-sequence parallel sequence alignment, combining a succinct WFA-data representation with an efficient GPU implementation. As a result, we demonstrate that our implementation outperforms the original multi-threaded WFA implementation by up to 4.3× and up to 18.2× when using heuristic methods on long and noisy sequences. Compared to other state-of-the-art tools and libraries, the WFA-GPU is up to 29× faster than other GPU implementations and up to four orders of magnitude faster than other CPU implementations. Furthermore, WFA-GPU is the only GPU solution capable of correctly aligning long reads using a commodity GPU.Availability and implementationWFA-GPU code and documentation are publicly available at https://github.com/quim0/WFA-GPU.

| S-EPMC10697739 | biostudies-literature

Fast and exact gap-affine partial order alignment with POASTA.

Project description:MotivationPartial order alignment is a widely used method for computing multiple sequence alignments, with applications in genome assembly and pangenomics, among many others. Current algorithms to compute the optimal, gap-affine partial order alignment do not scale well to larger graphs and sequences. While heuristic approaches exist, they do not guarantee optimal alignment and sacrifice alignment accuracy.ResultsWe present POASTA, a new optimal algorithm for partial order alignment that exploits long stretches of matching sequence between the graph and a query. We benchmarked POASTA against the state-of-the-art on several diverse bacterial gene datasets and demonstrated an average speed-up of 4.1× and up to 9.8×, using less memory. POASTA's memory scaling characteristics enabled the construction of much larger POA graphs than previously possible, as demonstrated by megabase-length alignments of 342 Mycobacterium tuberculosis sequences.Availability and implementationPOASTA is available on Github at https://github.com/broadinstitute/poasta.

| S-EPMC11755094 | biostudies-literature

GraphClust: alignment-free structural clustering of local RNA secondary structures.

Project description:MotivationClustering according to sequence-structure similarity has now become a generally accepted scheme for ncRNA annotation. Its application to complete genomic sequences as well as whole transcriptomes is therefore desirable but hindered by extremely high computational costs.ResultsWe present a novel linear-time, alignment-free method for comparing and clustering RNAs according to sequence and structure. The approach scales to datasets of hundreds of thousands of sequences. The quality of the retrieved clusters has been benchmarked against known ncRNA datasets and is comparable to state-of-the-art sequence-structure methods although achieving speedups of several orders of magnitude. A selection of applications aiming at the detection of novel structural ncRNAs are presented. Exemplarily, we predicted local structural elements specific to lincRNAs likely functionally associating involved transcripts to vital processes of the human nervous system. In total, we predicted 349 local structural RNA elements.AvailabilityThe GraphClust pipeline is available on request.

| S-EPMC3371856 | biostudies-literature

LocalSTAR3D: a local stack-based RNA 3D structural alignment tool.

Project description:A fast-growing number of non-coding RNA structures have been resolved and deposited in Protein Data Bank (PDB). In contrast to the wide range of global alignment and motif search tools, there is still a lack of local alignment tools. Among all the global alignment tools for RNA 3D structures, STAR3D has become a valuable tool for its unprecedented speed and accuracy. STAR3D compares the 3D structures of RNA molecules using consecutive base-pairs (stacks) as anchors and generates an optimal global alignment. In this article, we developed a local RNA 3D structural alignment tool, named LocalSTAR3D, which was extended from STAR3D and designed to report multiple local alignments between two RNAs. The benchmarking results show that LocalSTAR3D has better accuracy and coverage than other local alignment tools. Furthermore, the utility of this tool has been demonstrated by rediscovering kink-turn motif instances, conserved domains in group II intron RNAs, and the tRNA mimicry of IRES RNAs.

| S-EPMC7367197 | biostudies-literature

Local alignment refinement using structural assessment.

Project description:Homology modeling is the most commonly used technique to build a three-dimensional model for a protein sequence. It heavily relies on the quality of the sequence alignment between the protein to model and related proteins with a known three dimensional structure. Alignment quality can be assessed according to the physico-chemical properties of the three dimensional models it produces. In this work, we introduce fifteen predictors designed to evaluate the properties of the models obtained for various alignments. They consist of an energy value obtained from different force fields (CHARMM, ProsaII or ANOLEA) computed on residue selected around misaligned regions. These predictors were evaluated on ten challenging test cases. For each target, all possible ungapped alignments are generated and their corresponding models are computed and evaluated. The best predictor, retrieving the structural alignment for 9 out of 10 test cases, is based on the ANOLEA atomistic mean force potential and takes into account residues around misaligned secondary structure elements. The performance of the other predictors is significantly lower. This work shows that substantial improvement in local alignments can be obtained by careful assessment of the local structure of the resulting models.

| S-EPMC2440426 | biostudies-literature

FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity

Project description: Not available

| S-EPMC11846685 | biostudies-literature

Affine Deformation and Self-Assembly Alignment in Hydrogel Nanocomposites.

Project description:Tailoring the order in hierarchical structures is a key goal of bioinspired nanocomposite design. Recently, nacre-like materials have been developed by solvent evaporation methods that are scalable and attain advanced functionalities. However, understanding the alignment mechanisms of 2D fillers, nanosheets, or platelets remains challenging. This work explores possible pathways for nanocomposite ordering via orientation distribution functions. We demonstrate how the immobilization of 2D materials via (pseudo)network formation is crucial to alignment based on evaporation. We show a modified affine deformation model that describes such evaporative methods. In this, a gel network develops enough yield stress and uniformly deforms as drying proceeds, along with the immobilized particles, causing an in-plane orientation. Herein, we tested the dominance of this approach by using a thermo-reversible gel for rapid montmorillonite (MMT) particle fixation. We researched gelatin/MMT as a model system to investigate the effects of high loadings, orientational order, and aspect ratio. The nacre-like nanocomposites showed a semiconstant order parameter (⟨P2⟩ ∼ 0.7) over increasing nanofiller content up to 64 vol % filler. This remarkable alignment resulted in continuously improved mechanical and water vapor barrier properties over unusually large filler fractions. Some variations in stiffness and diffusion properties were observed, possibly correlated to the applied drying conditions of the hybrid hydrogels. The affine deformation strategy holds promise for developing next-generation advanced materials with tailored properties even at (very) high filler loadings. Furthermore, a gelling approach offers the advantages of simplicity and versatility in the formulation of the components, which is useful for large-scale fabrication methods.

| S-EPMC10720479 | biostudies-literature

Local RNA structure alignment with incomplete sequence.

Project description:MotivationAccuracy of automated structural RNA alignment is improved by using models that consider not only primary sequence but also secondary structure information. However, current RNA structural alignment approaches tend to perform poorly on incomplete sequence fragments, such as single reads from metagenomic environmental surveys, because nucleotides that are expected to be base paired are missing.ResultsWe present a local RNA structural alignment algorithm, trCYK, for aligning and scoring incomplete sequences under a model using primary sequence conservation and secondary structure information when possible. The trCYK algorithm improves alignment accuracy and coverage of sequence fragments of structural RNAs in simulated metagenomic shotgun datasets.AvailabilityThe source code for Infernal 1.0, which includes trCYK, is available at http://infernal.janelia.org.

| S-EPMC2677745 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data