UNIT 2 (ALGORITHMS IN COMPUTATIONAL BIOLOGY)

DALI AND HMM

DALI (Distance-matrix ALIgnment) and Hidden Markov Models (HMM) are foundational
computational frameworks for analyzing biological sequences and structures, including their
application to RNA structure prediction. These methods bring distinctive mathematical and
algorithmic perspectives to revealing structural relationships and inferring hidden biological
states from experimental data, making them highly relevant in advanced bioinformatics
studies targeting RNA secondary and tertiary [Link]+1

DALI: Principles and Algorithm Overview

DALI is primarily designed for comparing macromolecular 3D structures by aligning

distance matrices derived from their atomic coordinates. Originally devised for proteins,
DALI's core ideas have influenced various structure-alignment approaches, and analogous
principles may be leveraged in RNA structural analysis, especially as the number of
experimentally determined RNA structures [Link]+2

DALI represents each macromolecule as a distance matrix, where each cell records the spatial
distance between two atoms (typically C-alpha atoms in proteins, or analogous backbone
atoms in RNA). The comparison of two structures thus reduces to finding an optimal
alignment between their respective distance matrices. This comparison uses a scoring
function that rewards similarity in intramolecular distances but also tolerates local deviations
(e.g., from loop mobility or torsion), accommodating the inherent flexibility of
macromolecular [Link]+1

Algorithm Steps

 DALI computes pairwise distance matrices from the atomic coordinates of two
candidate structures.
 The algorithm heuristically aligns these matrices to maximize a similarity score,
which is a weighted sum over matching pairs of atom distances.
  The method employs dynamic programming-like heuristics because the full search
space is exponential; it efficiently detects core structural similarities even if global
alignment isn't perfect.
 The scoring allows for both positive and negative contributions, so only the 'common
core' where similarity is highest gets high [Link]+1

Applications in RNA

While DALI is mostly associated with protein comparison, RNA structure comparison
presents similar mathematical challenges — namely, the flexible but recurrent arrangement of
structural motifs like helices, loops, and pseudoknots. By adapting DALI-like frameworks,
one can compare the backbone geometry of RNAs, detect shared folds, or even discover
evolutionary relationships based on tertiary architecture. Contemporary work sometimes
integrates DALI-style metrics to cross-validate predictions made by sequence-based tools, or
to cluster RNA folds for phylogenetic, functional, or classification [Link]+1

Hidden Markov Models (HMM) in RNA Structure Prediction

Hidden Markov Models offer a probabilistic framework for modeling sequences of observed
events (such as nucleotides in RNA) that are generated by a sequence of hidden states (such
as structural features or base pairing types). HMMs have proven crucial in many areas of
computational biology, including RNA secondary structure [Link]+2

HMM Fundamentals

An HMM consists of:

 A set of hidden states, each representing a possible underlying condition at a given

position (e.g., a nucleotide being paired/unpaired, or belonging to a specific
substructure).
 Emission probabilities that link each hidden state to observable symbols (nucleotides
A, U, G, C).
 Transition probabilities defining the likelihood of moving from one hidden state to
another.
Inference in HMMs (e.g., with the Viterbi algorithm) enables decoding the most probable
sequence of hidden states — which, in the RNA context, amounts to predicting the most
likely secondary [Link]+2

Extensions for RNA Structure

Classic HMMs capture only local, Markovian dependencies (the state at position i depends on
position i-1). More complex RNA structures (such as pseudoknots) require models
accommodating long-range dependencies. The α-HMM generalizes the traditional HMM by
including arbitrary-order dependencies (influences) between non-adjacent states, making it
suitable for capturing the crossing base pairing patterns of RNA pseudoknots and other non-
nested [Link]+1

This approach extends HMMs beyond the expressivity of stochastic context-free grammars
(SCFGs), which are also widely used but limited to nested base pairings. Advanced decoding
algorithms, usually invariant under O(n³) time for an RNA of length n, leverage dynamic
programming while incorporating these long-range 'influence edges' to maximize the joint
probability of the observed sequence and structure. This enables accurate prediction of both
canonical and non-canonical pairing patterns, including stem-loops, multi-loops, and
[Link]+2

Role in Modern RNA Prediction Pipelines

HMMs and their variants serve as the statistical backbone for various tools that infer RNA
structure:

 They offer robust frameworks for integrating sequence conservation, covariation, and
experimental constraints.
 Hybrid or ensemble models combine HMMs with machine learning or deep learning
modules for improved predictive accuracy, interpretability, and flexibility.
 In addition to secondary structure annotation, HMMs can classify RNA families,
identify functional motifs, and even infer tertiary interactions by layering models for
different structural [Link]+2

Integration of DALI and HMM Concepts

Although DALI and HMM stem from different traditions (geometric vs. statistical modeling),
their integration is increasingly feasible and desirable in RNA structural bioinformatics:

 DALI-type geometric comparisons help validate or refine RNA structure predictions

generated by HMMs or SCFGs, providing 3D spatial context that pure sequence
models may [Link]+1
 HMM-based methods, enriched with long-range dependencies (as in α-HMM),
generate candidate structural models that, when mapped onto 3D atomic coordinates,
can be quantitatively evaluated using DALI-like alignment scores, closing the loop
between sequence consensus and biophysical [Link]+1
 This integrative potential is vital for de novo RNA design, evolutionary studies, and
the annotation of noncoding RNAs, ribozymes, and synthetic constructs for
biomedical [Link]+1

Emerging Trends and Challenges

Recent developments further enhance the joint use of DALI and HMM approaches in RNA
structure prediction:

 Deep generative models and AI-driven methods often encode HMM-like architectures
within larger neural networks, facilitating end-to-end learning of RNA structure from
raw [Link]
 The expansion of experimentally determined RNA 3D structures offers more
templates for DALI-type alignment and benchmarking, improving the reliability of
statistical [Link]+1
 Despite advances, challenges remain: predicting pseudoknots, integrating sparse or
noisy experimental data, and scaling methods to very large RNA molecules or
transcriptomes.

Summary Table: DALI vs. HMM for RNA Structure

Feature DALI HMM/α-HMM

3D structure Sequence-to-structure
Primary Domain
[Link]+1 inferencearxiv

Input 3D atomic [Link] RNA nucleotide sequence

 Structural similarity, fold Base pairing, secondary
Output
[Link] structurearxiv

Mathematical Distance matrix alignment, Probabilistic graphical

Approach [Link] modelarxiv

Handles
Indirectly (with RNA geometries)nature Yes, with α-HMMarxiv
Pseudoknots

Main Application Predict base pairs, annotate

Validate/compare 3D foldsnature
in RNA motifsarxiv

Struggles with long-range

Needs experimental 3D
Limitation dependencies (classic
[Link]
HMM)arxiv

Integration with graphical user interfaces, α-HMM for crossing pairs and
Recent Advances
large databasesnature efficient O(n³) predictionarxiv

Conclusion

DALI and Hidden Markov Models are complementary pillars of computational RNA
structure prediction. DALI provides a gold-standard reference for three-dimensional
validation and discovery of novel folds, while HMM frameworks, especially with modern
extensions like α-HMM, enable accurate and efficient inference of secondary structure,
including challenging pseudoknots. Methodological synergy and continuous advances
promise robust, scalable, and interpretable tools for RNA structural biology in the era of big
biological [Link]+2

1. [Link]
2. [Link]
3. [Link]
4. [Link]
content/uploads/sites/162/2017/11/DALI_Mark_2016.pdf
5. [Link]
6. [Link]
7. [Link]
8. [Link]
9. [Link]
10. [Link]
11. [Link]
12. [Link]
13. [Link]
14. [Link]
15. [Link]
16. [Link]
17. [Link]
18. [Link]
19. [Link]
20. [Link]

DIVIDE AND CONQUER

The divide and conquer algorithm is a powerful strategy in computer science and
bioinformatics for solving complex problems by recursively breaking them into smaller, more
manageable subproblems, solving each independently, and then combining their solutions for
a complete answer. This paradigm underpins many classic algorithms, such as Merge Sort
and Quick Sort, and plays a significant role in the design of efficient algorithms for biological
data analysis, especially when dealing with large-scale datasets like genomes, protein
structures, or evolutionary [Link]+2

Principles of Divide and Conquer

At its core, divide and conquer comprises three main steps:

 Divide: The original problem is partitioned into smaller, usually similar,

subproblems.
 Conquer: Each subproblem is solved independently, often recursively, until reaching
a base case that is trivial to solve.
 Combine: The solutions to the subproblems are merged or synthesized to form the
solution to the original [Link]+1

This recursive breakdown is particularly suitable when large, complex datasets must be
processed, for example, in sequence alignment, phylogenetic inference, or NGS read
[Link]+1

Example: Divide and Conquer in NGS Read Alignment

A prominent application of divide and conquer in biological data is in next-generation

sequencing (NGS) read alignment. Large-scale sequencing produces millions of DNA
fragments (reads) that need to be mapped rapidly and accurately to a reference genome.
Efficient alignment becomes challenging as the length and number of reads increase,
especially for long or error-prone sequences.

The Kart algorithm is a notable example that employs divide and conquer for read
alignment. Kart splits each read into smaller, independently alignable fragments (subreads).
The algorithm treats perfectly matching segments as "simple pairs" that can be quickly
mapped, while more ambiguous fragments are handled separately and precisely. This strategy
drastically reduces computational time without sacrificing accuracy, even when working with
high error rates or very long [Link]

Steps in the Divide and Conquer Read Alignment (Kart)

 The full read is divided into subreads or fragments.

 Each fragment is aligned individually; easy-to-align fragments are quickly placed,
while only a few difficult regions require complex (gapped) alignment.
 The overall alignment is constructed by combining the aligned fragments, resolving
overlaps and adjusting for small indels or mismatches.

By localizing complex computation to small areas, the whole read can be mapped swiftly and
robustly, highlighting the practicality and effectiveness of divide and conquer in modern
[Link]

Other Common Bioinformatics Examples

 Multiple sequence alignment: Large-scale alignments (ClustalW, T-Coffee) often

use divide and conquer by breaking up the set of sequences, aligning in subgroups,
and merging alignments [Link]
 Phylogenetic network inference: Large networks are inferred by constructing small
subnetworks (e.g., on trinets or quartets) then incrementally merging them to create
the full evolutionary history. This approach drastically improves scalability for
datasets with hundreds or thousands of [Link]
 Linear space sequence alignment: Hirschberg’s algorithm applies divide and
conquer to generate an optimal sequence alignment with linear space
requirements—an essential innovation when dealing with massive genetic
[Link]

Advantages of Divide and Conquer in Biological Data

 Scalability: Subdividing large problems means that solutions scale efficiently,

enabling the analysis of entire genomes or large phylogenetic [Link]+1
 Reduced Space Complexity: Many classical dynamic programming algorithms
require O(mn) space (m, n: sequence lengths). Divide and conquer can often achieve
 O(m+n) space, making it feasible to process long sequences (as in Hirschberg’s
algorithm).[Link]
 Parallelism: Subproblems are often independent and can be solved in parallel,
leveraging modern multicore and distributed computing resources for massive
biological datasets.
 Localized Error Handling: Errors or ambiguous regions can be isolated; only small
problematic fragments are subjected to expensive detailed analysis, boosting overall
efficiency (as seen in Kart's handling of high-error reads).[Link]

Disadvantages and Challenges

 Complexity of Combination Step: The most challenging part is often merging the
solutions of subproblems. Overlaps, inconsistencies, or errors may arise during
recombination, especially in sequence alignment or phylogenetic
[Link]
 Overhead: If the divide step leads to too many subproblems or if subproblems are not
significantly simpler than the original, the overhead can outweigh the benefits. There
may also be redundancy in computation between subproblems.
 Diminishing Returns on Small Datasets: For small or trivially sized datasets, the
recursive division may introduce unnecessary overhead compared to simpler iterative
solutions.
 Non-Uniform Data: In biological datasets, regions may vary greatly in complexity
(e.g., repetitive vs. unique DNA). Uniform division might not reflect true underlying
structure, potentially leading to inefficiencies.

Biological Data Example: Phylogenetic Network Inference

Suppose researchers want to infer the complex evolutionary history (“network”) of several
species from multi-locus sequence alignments. A divide and conquer approach can be
outlined as follows:[Link]

 Divide: Group species into overlapping subsets (such as every possible trinet—group
of three taxa).
 Conquer: Infer a small phylogenetic network for each subset using likelihood-based
or heuristic methods.
  Combine: Sequentially merge these subnetworks to reconstruct the full phylogenetic
network, reconciling conflicting topologies and timestamps.

This approach allows scalable inference for hundreds of taxa—otherwise infeasible with
traditional methods—by enabling parallel computation and limiting combinatorial explosion
to manageable subgroups.

However, combining subnetworks requires careful handling of overlaps and conflicts, and
there are trade-offs between accuracy and computational cost, especially as the number and
size of subproblems [Link]

Conclusion

Divide and conquer algorithms are a cornerstone of scalable, efficient bioinformatics,

facilitating the analysis of large biological data through recursive problem reduction. Their
application in sequence alignment, read mapping, and phylogenetic inference illustrates both
the power and the inherent trade-offs of the approach. Properly exploited, divide and conquer
delivers major gains in speed, memory usage, and parallelizability, with combination
complexity and dataset non-uniformity posing the main ongoing
[Link]+2

1. [Link]
content/uploads/2016/08/Ch07_DnC_LinearSpaceAlignment.pdf
2. [Link]
3. [Link]
4. [Link]
5. [Link]
6. [Link]
[Link]
7. [Link]
conquer-algorithms
8. [Link]