Related Experiment Video
Updated: Jun 21, 2026
06:45
Design and Application of a Fault Detection Method Based on Adaptive Filters and Rotational Speed Estimation for an Electro-Hydrostatic Actuator
Published on: October 28, 2022
An approximation algorithm for the minimum breakpoint linearization problem
1Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore. chenxin@ntu.edu.sg
Summary
This study introduces a new approximation algorithm for the Minimum Breakpoint Linearization (MBL) problem in genome rearrangement. The algorithm provides a guaranteed performance bound for ordering genes on a chromosome from partial data.
Area of Science:
- Computational Biology
- Genomics
- Bioinformatics
Background:
- Genetic mapping often yields partial gene orders, necessitating methods to infer complete chromosomal sequences.
- Genome rearrangement problems, including Minimum Breakpoint Linearization (MBL), are crucial for understanding genome evolution and structure.
- The MBL problem aims to find a total gene order minimizing breakpoint distance to a reference, but is known to be NP-hard.
Purpose of the Study:
- To develop an efficient approximation algorithm for the Minimum Breakpoint Linearization (MBL) problem.
- To provide a theoretical performance guarantee for inferring total gene order from partial data.
Main Methods:
- Formulation of the Minimum Breakpoint Linearization (MBL) problem within genome rearrangement.
- Development of a novel approximation algorithm with a specific performance bound.
- Analysis of the algorithm's approximation ratio: {m(2)+m/2}, where m is the number of combined gene maps.
Main Results:
- The proposed algorithm achieves an {m(2)+m/2}-approximation for the MBL problem.
- This represents an improvement over existing heuristic approaches by providing a quantifiable performance guarantee.
- The algorithm effectively addresses the challenge of inferring total gene order from incomplete genetic mapping data.
Conclusions:
- The developed algorithm offers a significant advancement in solving the NP-hard MBL problem.
- It provides a practical and theoretically sound method for reconstructing complete gene orders from partial genomic information.
- This contributes to more accurate genome assembly and comparative genomics studies.
More Related Videos
Related Concept Videos
01:26Linearization and Approximation
Linearization is a mathematical technique used to approximate complex, nonlinear functions with simpler linear models in the vicinity of a chosen reference point. The method is based on the idea that, although a function may be difficult to evaluate exactly, its behavior near a specific input value can often be closely approximated by the tangent line at that point. This approach is particularly useful when small deviations from a known value are involved.Consider the square root function, for...
01:29Application of Linearization and Approximation
A drone flying through complex terrain often relies on more than one sensing method to estimate small changes in altitude. Along with direct measurements, air pressure provides a useful indirect indicator of vertical movement. Atmospheric pressure decreases as altitude increases, and this relationship is commonly described using an exponential model. Although accurate, converting pressure measurements into altitude values requires calculations that are too complex to perform repeatedly during...
01:23Linear Approximations
For a differentiable function of two variables, linear approximation estimates values near a known point by replacing the curved surface with its tangent plane. Consider the function\begin{equation*}f(x,y)=x^2+3y^2\end{equation*}near the point (2, 1). The exact value at this point is f(2, 1) = 22 + 3(1)2 = 4 + 3 = 7.The linear approximation of f(x, y)) near (a, b) is\begin{equation*}L(x,y)=f(a,b)+f_x(a,b)(x-a)+f_y(a,b)(y-b)\end{equation*}First, compute the partial derivatives: fx(x, y) = 2x and...
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
01:21Linear Approximation in Time Domain
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, the...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length, the...
01:26Linear Approximation in Frequency Domain
Linear systems are characterized by two main properties: superposition and homogeneity. Superposition allows the response to multiple inputs to be the sum of the responses to each individual input. Homogeneity ensures that scaling an input by a scalar results in the response being scaled by the same scalar.
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear.
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear.