Related Experiment Video
Updated: Jun 6, 2026
11:22
Automated Robotic Liquid Handling Assembly of Modular DNA Devices
Published on: December 1, 2017
Effective haplotype assembly via maximum Boolean satisfiability
Sayyed R Mousavi1, Maryam Mirabolghasemi, Nadia Bargesteh
1Department of Computer Engineering and Information Technology, Isfahan University of Technology, Isfahan 84156-83111, Iran. srm@cc.iut.ac.ir
Biochemical and Biophysical Research Communications
|December 15, 2010
Summary
This study introduces a new Max-2-SAT formulation to solve the complex haplotype assembly problem. Our method significantly improves the quality of haplotype solutions, offering a more effective approach for genetic studies.
Area of Science:
- Computational Biology
- Bioinformatics
- Genetics
Background:
- Haplotype assembly is crucial for understanding genetic variations and disease associations.
- The Minimum Error Correction objective makes haplotype assembly an NP-hard problem.
- Existing algorithms struggle to provide consistently high-quality solutions.
Purpose of the Study:
- To develop a novel and effective method for haplotype assembly.
- To address the computational complexity of the haplotype assembly problem.
- To improve the accuracy and quality of assembled haplotypes.
Main Methods:
- Formulation of the haplotype assembly problem as a novel Max-2-SAT problem.
- Implementation and comparison of the proposed Max-2-SAT method.
- Evaluation on an extensive benchmark dataset against existing algorithms.
Main Results:
- The proposed Max-2-SAT method consistently outperformed existing algorithms.
- Achieved solutions of higher average quality in haplotype assembly.
- Demonstrated the effectiveness of the novel formulation for this NP-hard problem.
Conclusions:
- The novel Max-2-SAT formulation provides a superior approach to haplotype assembly.
- This method offers a more effective and accurate solution for genetic studies.
- The findings advance computational methods in bioinformatics and genetics.
Related Concept Videos
03:36Genome Annotation and Assembly
The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.
02:41Protein Complex Assembly
Proteins can form homomeric complexes with another unit of the same protein or heteromeric complexes with different types. Most protein complexes self-assemble spontaneously via ordered pathways, while some proteins need assembly factors that guide their proper assembly. Despite the crowded intracellular environment, proteins usually interact with their correct partners and form functional complexes.
Many viruses self-assemble into a fully functional unit using the infected host cell to...
Many viruses self-assemble into a fully functional unit using the infected host cell to...
01:11Genome-wide Association Studies-GWAS
Genome-wide association studies or GWAS are used to identify whether common SNPs are associated with certain diseases. Suppose specific SNPs are more frequently observed in individuals with a particular disease than those without the disease. In that case, those SNPs are said to be associated with the disease. Chi-square analysis is performed to check the probability of the allele likely to be associated with the disease.
GWAS does not require the identification of the target gene involved in...
GWAS does not require the identification of the target gene involved in...