Related Experiment Video
Updated: Feb 8, 2026
10:34
Ultra-long Read Sequencing for Whole Genomic DNA Analysis
Published on: March 15, 2019
24.0K
Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics
Summary
Extending sequence alignment to pan-genome graphs and diploid genomes presents new computational challenges. Finding covering alignments for labeled directed acyclic graphs (DAGs) is NP-hard, impacting genomic sequence analysis.
Area of Science:
- Computational Biology
- Genomics
- Bioinformatics
Background:
- Genomic analysis is shifting from reference genomes to pan-genome graphs.
- Haplotyping advances allow for the use of complete diploid genome content in sequence analysis.
- Traditional sequence alignment methods face challenges with these new genomic representations.
Purpose of the Study:
- To investigate the computational complexity of sequence alignment extensions for pan-genome graphs and diploid genomes.
- To analyze the complexity of covering alignments on labeled directed acyclic graphs (DAGs).
- To model the similarity of two diploids over arbitrary recombinations using covering alignments.
Main Methods:
- Formulating sequence alignment as a covering alignment problem on labeled DAGs.
- Proving the NP-hardness of finding covering alignments for two labeled DAGs, even on binary alphabets.
- Reducing diploid genome alignment to a two-path coverable labeled DAG problem.
Main Results:
- Finding a covering alignment of two labeled DAGs is NP-hard.
- The problem remains NP-hard even for binary alphabets.
- Recombination-oblivious diploid alignment is NP-hard on alphabets of size 3.
Conclusions:
- Extending sequence alignment to pan-genome graphs and diploid genomes significantly increases computational complexity.
- The covering alignment framework provides a model for analyzing diploid genome similarity under recombination.
- New algorithmic approaches are needed to address these NP-hard problems in genomics.
Related Concept Videos
02:31Phase Transitions
23.2K
Whether solid, liquid, or gas, a substance's state depends on the order and arrangement of its particles (atoms, molecules, or ions). Particles in the solid pack closely together, generally in a pattern. The particles vibrate about their fixed positions but do not move or squeeze past their neighbors. In liquids, although the particles are closely spaced, they are randomly arranged. The position of the particles are not fixed—that is, they are free to move past their neighbors to...
23.2K
02:33Phase Transitions: Sublimation and Deposition
20.2K
Some solids can transition directly into the gaseous state, bypassing the liquid state, via a process known as sublimation. At room temperature and standard pressure, a piece of dry ice (solid CO2) sublimes, appearing to gradually disappear without ever forming any liquid. Snow and ice sublimate at temperatures below the melting point of water, a slow process that may be accelerated by winds and the reduced atmospheric pressures at high altitudes. When solid iodine is warmed, the solid sublimes...
20.2K
02:39Phase Transitions: Melting and Freezing
15.2K
Heating a crystalline solid increases the average energy of its atoms, molecules, or ions, and the solid gets hotter. At some point, the added energy becomes large enough to partially overcome the forces holding the molecules or ions of the solid in their fixed positions, and the solid begins the process of transitioning to the liquid state or melting. At this point, the temperature of the solid stops rising, despite the continual input of heat, and it remains constant until all of the solid is...
15.2K
02:39Phase Transitions: Vaporization and Condensation
21.5K
The physical form of a substance changes on changing its temperature. For example, raising the temperature of a liquid causes the liquid to vaporize (convert into vapor). The process is called vaporization—a surface phenomenon. Vaporization occurs when the thermal motion of the molecules overcome the intermolecular forces, and the molecules (at the surface) escape into the gaseous state. When a liquid vaporizes in a closed container, gas molecules cannot escape. As these gas phase molecules...
21.5K
02:58Properties of Transition Metals
30.0K
Transition metals are defined as those elements that have partially filled d orbitals. As shown in Figure 1, the d-block elements in groups 3–12 are transition elements. The f-block elements, also called inner transition metals (the lanthanides and actinides), also meet this criterion because the d orbital is partially occupied before the f orbitals.
30.0K
02:02Genomics
40.8K
Genomics is the science of genomes: it is the study of all the genetic material of an organism. In humans, the genome consists of information carried in 23 pairs of chromosomes in the nucleus, as well as mitochondrial DNA. In genomics, both coding and non-coding DNA is sequenced and analyzed. Genomics allows a better understanding of all living things, their evolution, and their diversity. It has a myriad of uses: for example, to build phylogenetic trees, to improve productivity and...
40.8K