Related Experiment Video
Updated: May 12, 2026
10:23
A Concoction Pipeline for Generating Molecular Operational Taxonomic Units (MOTUs) Among Riparian and Aquatic Beetles
Published on: July 11, 2025
Unrooted unordered homeomorphic subtree alignment of RNA trees
Nimrod Milo1, Shay Zakov2, Erez Katzenelson1
1Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel.
Algorithms for Molecular Biology : AMB
|April 18, 2013
Summary
This study introduces a generalized algorithm for RNA tree alignment, enabling unordered and unrooted mappings. The new approach enhances the detection of structural similarities in RNA, outperforming traditional methods.
Area of Science:
- Bioinformatics and Computational Biology
- Structural Biology
- RNA Structure Analysis
Background:
- Current RNA tree alignment methods are primarily limited to ordered and rooted mappings.
- These limitations restrict the ability to detect diverse structural similarities in RNA molecules.
- There is a need for more generalized alignment approaches to capture a wider range of RNA structures.
Purpose of the Study:
- To generalize RNA tree alignment algorithms beyond ordered rooted mappings.
- To introduce and solve the Homeomorphic Subtree Alignment (HSA) problem for various alignment modes.
- To develop a novel algorithm capable of handling unrooted and unordered tree alignments.
Main Methods:
- Developed a new algorithm for the Homeomorphic Subtree Alignment (HSA) problem, supporting global/local, ordered/unordered, and rooted/unrooted alignments.
- Introduced and solved generalized variants of the Min-Cost Bipartite Matching (MCM) problem, including All-Cavity-MCM and All-Pairs-Cavity-MCM.
- Achieved an O(nTnS + min(dT,dS)LTLS) time complexity for the unrooted unordered case, improving upon previous algorithms.
Main Results:
- The new algorithm successfully generalizes existing RNA tree alignment approaches.
- New algorithms for MCM and its cavity variants achieve O(n^3 + nm) time complexity, improving efficiency for unbalanced cases.
- A software tool implementing the algorithm revealed new similarities between RNAse P and Hammerhead RNA families, missed by traditional methods.
Conclusions:
- The generalized HSA algorithm offers a more sensitive approach to detecting structural similarities in RNA.
- The developed MCM algorithms provide efficient solutions for complex matching problems.
- The tool demonstrates practical utility in uncovering previously undetected RNA structural relationships.
Related Concept Videos
03:21Phylogenetic Trees
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.
03:21Phylogenetic Trees
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.
01:28Microbial Phylogeny
Understanding the evolutionary relationships among microorganisms is fundamental to microbial ecology and taxonomy. Phylogenetic trees are essential tools for inferring these relationships, relying primarily on comparative analyses of molecular sequences such as DNA, RNA, or proteins. In microbial studies, these trees typically depict the evolutionary paths of diverse bacterial and archaeal species by mapping genetic differences accumulated over time.Phylogenetic trees are composed of tips,...
02:54Evolutionary Relationships through Genome Comparisons
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
01:19RNA Structure
The basic structure of RNA consists of a string of ribonucleotides attached by phosphodiester bonds. Although most RNA is single-stranded, it can form complex secondary and tertiary structures. Such structures play essential roles in the regulation of transcription and translation.
Different Types of RNA Have the Same Basic Structure
There are three main types of ribonucleic acid (RNA) involved in protein synthesis: messenger RNA (mRNA), transfer RNA (tRNA), and ribosomal RNA (rRNA). All three...
Different Types of RNA Have the Same Basic Structure
There are three main types of ribonucleic acid (RNA) involved in protein synthesis: messenger RNA (mRNA), transfer RNA (tRNA), and ribosomal RNA (rRNA). All three...
01:23RNA Structure
Overview
The basic structure of RNA consists of a five-carbon sugar and one of four nitrogenous bases. Although most RNA is single-stranded, it can form complex secondary and tertiary structures. Such structures play essential roles in the regulation of transcription and translation.
Different Types of RNA Have the Same Basic Structure
There are three main types of ribonucleic acid (RNA): messenger RNA (mRNA), transfer RNA (tRNA), and ribosomal RNA (rRNA). All three RNA types consist of a...
The basic structure of RNA consists of a five-carbon sugar and one of four nitrogenous bases. Although most RNA is single-stranded, it can form complex secondary and tertiary structures. Such structures play essential roles in the regulation of transcription and translation.
Different Types of RNA Have the Same Basic Structure
There are three main types of ribonucleic acid (RNA): messenger RNA (mRNA), transfer RNA (tRNA), and ribosomal RNA (rRNA). All three RNA types consist of a...