Related Experiment Video
Updated: Feb 11, 2026
10:54
Detection of Retrotransposition Activity of Hot LINE-1s by Long-Distance Inverse PCR
Published on: July 27, 2019
9.1K
A Simple Linear Space Algorithm for Computing Nonoverlapping Inversion and Transposition Distance in Quadratic
11 Fujian University of Technology , Fuzhou, China .
Summary
This study introduces a novel algorithm for DNA sequence alignment, specifically addressing nonoverlapping inversions and transpositions. It achieves linear space complexity for computing mutation distance, a significant improvement over existing quadratic space methods.
Area of Science:
- Bioinformatics and Computational Biology
- Genomics and Sequence Analysis
Background:
- Sequence alignment is crucial for retrieving information from DNA sequences.
- Inversions and translocations are key operations in biosequence analysis.
- The alignment problem with nonoverlapping inversions and translocations is vital for identifying common sequences in mutated DNA.
Purpose of the Study:
- To present a novel algorithm for computing mutation distance between two DNA strings.
- To address the alignment problem incorporating nonoverlapping inversions and transpositions.
- To develop a linear space algorithm for this specific biosequence analysis task.
Main Methods:
- Development of a linear space, quadratic average time algorithm.
- Utilizing a novel recursive formula for mutation distance calculation.
- Focusing on nonoverlapping inversions and transpositions in sequence alignment.
Main Results:
- The proposed algorithm computes mutation distance efficiently.
- Achieved linear space complexity, a first for this problem.
- Demonstrated quadratic average time performance.
Conclusions:
- The novel algorithm offers a significant advancement in sequence alignment.
- Linear space complexity is a key breakthrough, reducing memory requirements.
- The method is applicable to finding common sequences from mutated DNA.
Related Concept Videos
02:13Overview of Transposition and Recombination
19.4K
Transposons make up a significant part of genomes of various organisms. Therefore, it is believed that transposition played a major evolutionary role in speciation by changing genome sizes and modifying gene expression patterns. For example, in bacteria, transposition can lead to conferring antibiotic resistance. Movement of transposable elements within the genetic pool of pathogenic bacteria can aid in transfer of antibiotic-resistant genetic elements. In eukaryotes, transposons can carry out...
19.4K
01:23Linear time-invariant Systems
939
A system is linear if it displays the characteristics of homogeneity and additivity, together termed the superposition property. This principle is fundamental in all linear systems. Linear time-invariant (LTI) systems include systems with linear elements and constant parameters.
The input-output behavior of an LTI system can be fully defined by its response to an impulsive excitation at its input. Once this impulse response is known, the system's reaction to any other input can be...
The input-output behavior of an LTI system can be fully defined by its response to an impulsive excitation at its input. Once this impulse response is known, the system's reaction to any other input can be...
939
01:21Linear Approximation in Time Domain
378
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
378
01:29Quadratic Equations
376
A quadratic equation is an algebraic expression where a variable is raised to the second power and combined with its first power and a constant; all equated to zero. These equations are frequently used to model relationships involving area, motion, and optimization. The general representation of a quadratic equation iswhere a, b, and c are real values, and a is nonzero to ensure the presence of the squared term.One method for solving a quadratic equation involves rewriting it as a product of...
376
01:23Quadratic Models
248
Quadratic models are mathematical representations used to describe relationships in which the rate of change changes at a constant rate. These models appear in a wide variety of natural and engineered systems, especially those involving motion, forces, and optimization. One common application is analyzing the vertical motion of objects influenced by gravity, such as a ball thrown into the air.In such scenarios, the object's height changes over time in a curved pattern, rising to a maximum point...
248
01:12Voltammetric Techniques: Linear-Scan (E vs Time)
1.3K
Polarography is a classical voltammetric technique used to analyze electrochemical reactions. This method applies a linear potential sweep to a dropping mercury electrode (DME), and the resulting current is measured. A dropping mercury electrode is commonly used as the working electrode in polarography. It consists of a capillary tube filled with mercury, where the tiny droplet forms at the tip. This droplet continuously drops from the capillary, creating a new electrode surface for each...
1.3K