Related Experiment Video
Updated: Aug 19, 2025
07:08
Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
Published on: July 14, 2015
7.4K
On the Hardness of Sequence Alignment on De Bruijn Graphs
Daniel Gibney1, Sharma V Thankachan2, Srinivas Aluru1
1School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, Georgia, USA.
Summary
Approximate pattern matching on de Bruijn graphs is NP-complete, even with only substitutions allowed. This contrasts with exact matching, which is linear time, highlighting challenges in computational biology sequence alignment.
Area of Science:
- Computational Biology
- Graph Theory
- Algorithm Complexity
Background:
- Sequence alignment in labeled graphs is crucial for computational biology.
- Exact matching on de Bruijn graphs is efficient (linear time).
- Approximate matching complexity varies: linear for acyclic graphs or pattern-only edits, NP-complete for general cyclic graphs.
Purpose of the Study:
- Investigate the complexity of approximate pattern matching on de Bruijn graphs.
- Determine if efficient approximate matching algorithms exist for de Bruijn graphs, especially with substitutions.
- Clarify the computational challenges in sequence alignment for this important graph structure.
Main Methods:
- Formal analysis of computational complexity.
- Proof of NP-completeness for approximate matching on de Bruijn graphs with substitutions.
- Lower bound analysis based on the Strong Exponential Time Hypothesis for pattern-only edits.
Main Results:
- Approximate pattern matching on de Bruijn graphs with substitutions is NP-complete.
- Efficient algorithms faster than O(2^m) for substitutions only to the pattern on de Bruijn graphs are unlikely.
- The efficiency of exact matching on de Bruijn graphs does not extend to approximate matching.
Conclusions:
- De Bruijn graphs, while efficient for exact sequence matching, present significant computational hurdles for approximate matching.
- The NP-completeness result for substitutions-only approximate matching underscores the difficulty of biological sequence analysis in these structures.
- Further research may be needed to develop practical algorithms for approximate sequence alignment on de Bruijn graphs.
Related Concept Videos
01:05Maxam-Gilbert Sequencing
11.4K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
11.4K
01:24Sequence Networks of Rotating Machines
131
A Y-connected synchronous generator, grounded through a neutral impedance, is designed to produce balanced internal phase voltages with only positive-sequence components. The generator's sequence networks include a source voltage that is exclusively in the positive-sequence network. The sequence components of line-to-ground voltages at the generator terminals illustrate this configuration.
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
131
03:21Phylogenetic Trees
45.8K
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.
45.8K
02:54Evolutionary Relationships through Genome Comparisons
6.1K
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...
6.1K
01:19Routh-Hurwitz Criterion II
341
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
341
01:15Routh-Hurwitz Criterion I
307
Consider an electrical power grid, where stability is essential to prevent blackouts. The Routh-Hurwitz criterion is a valuable tool for assessing system stability under varying load conditions or faults. By analyzing the closed-loop transfer function, the Routh-Hurwitz criterion helps determine whether the system remains stable.
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
307