Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Haplotype assembly from aligned weighted SNP fragments.

Yu-Ying Zhao1, Ling-Yun Wu, Ji-Hong Zhang

  • 1Institute of Applied Mathematics, Academy of Mathematics and Systems Science, CAS, Beijing 100080, China. zhyuying@amss.ac.cn

Computational Biology and Chemistry
|July 30, 2005
PubMed
Summary

This study addresses the NP-hard haplotype assembly problem. A new COMPLETE WMLF (CWMLF) model and heuristic algorithm improve haplotype reconstruction accuracy, outperforming existing WMLF and MLF methods.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

[Clinical Characteristics and Prognosis Analysis of MDS-RS Patients with Wild-Type <i>SF3B1</i>].

Zhongguo shi yan xue ye xue za zhi·2026
Same author

Exploring the Lung-Liver Axis in Pulmonary Arterial Hypertension.

Comprehensive Physiology·2026
Same author

Corrigendum to "Recombinant OX40 attenuates neuronal apoptosis through OX40-OX40L/PI3K/AKT signaling pathway following subarachnoid hemorrhage in rats" [Experimental Neurology, 326 (2020), 113179-113,190/ PMID:31930990].

Experimental neurology·2026
Same author

Radiotherapy in Cervical Myeloid Sarcoma: A Case Report and Literature Discussion.

International journal of women's health·2026
Same author

Deficiency of Setd2 in mesenchymal stem cells facilitates the progression of myelodysplastic syndrome to leukemia.

Molecular medicine (Cambridge, Mass.)·2026
Same author

[Effect of total triterpenes from Chaenomelis Fructus on mitigating indomethacin-induced gastric mucosal injury by inhibiting inflammation, oxidative stress, and NLRP3-mediated pyroptosis].

Zhongguo Zhong yao za zhi = Zhongguo zhongyao zazhi = China journal of Chinese materia medica·2026

Area of Science:

  • Genomics
  • Computational Biology
  • Bioinformatics

Background:

  • Haplotype assembly is crucial for understanding diploid genomes.
  • Existing models like Minimum Letter Flips (MLF) and Weighted Minimum Letter Flips (WMLF) have limitations.
  • The general WMLF model is computationally challenging (NP-hard).

Purpose of the Study:

  • To investigate the computational complexity of WMLF.
  • To develop a novel formulation, COMPLETE WMLF (CWMLF), addressing multiple data errors.
  • To propose a heuristic algorithm for CWMLF and evaluate its performance.

Main Methods:

  • Proving the NP-hardness of the general WMLF model.
  • Developing a heuristic algorithm utilizing dynamic clustering.
  • Introducing the CWMLF model to incorporate various data error types.

Related Experiment Videos

Main Results:

  • The general WMLF model is confirmed as NP-hard, even without gaps.
  • The proposed heuristic algorithm demonstrates effective solutions for WMLF variants.
  • CWMLF model implementations show superior accuracy in haplotype reconstruction compared to WMLF and MLF.

Conclusions:

  • The CWMLF model offers a more robust approach to haplotype assembly.
  • The heuristic algorithm provides an efficient method for solving WMLF variants.
  • This work advances computational strategies for accurate diploid genome analysis.