Efficient algorithms for polyploid haplotype phasing

BMC Genomics
Dan HeLaxmi Parida

Abstract

Inference of haplotypes, or the sequence of alleles along the same chromosomes, is a fundamental problem in genetics and is a key component for many analyses including admixture mapping, identifying regions of identity by descent and imputation. Haplotype phasing based on sequencing reads has attracted lots of attentions. Diploid haplotype phasing where the two haplotypes are complimentary have been studied extensively. In this work, we focused on Polyploid haplotype phasing where we aim to phase more than two haplotypes at the same time from sequencing data. The problem is much more complicated as the search space becomes much larger and the haplotypes do not need to be complimentary any more. We proposed two algorithms, (1) Poly-Harsh, a Gibbs Sampling based algorithm which alternatively samples haplotypes and the read assignments to minimize the mismatches between the reads and the phased haplotypes, (2) An efficient algorithm to concatenate haplotype blocks into contiguous haplotypes. Our experiments showed that our method is able to improve the quality of the phased haplotypes over the state-of-the-art methods. To our knowledge, our algorithm for haplotype blocks concatenation is the first algorithm that leverages the shar...Continue Reading

References

May 11, 2002·Briefings in Bioinformatics·Ross LippertSorin Istrail
Jun 19, 2007·Nature Genetics·Jonathan MarchiniPeter Donnelly
Aug 5, 2008·Genome Research·Vikas BansalVineet Bafna
Aug 12, 2008·Bioinformatics·Vikas Bansal, Vineet Bafna
Oct 31, 2008·Genome Research·Alexander GusevItsik Pe'er
Mar 23, 2010·American Journal of Human Genetics·Sharon R Browning, Brian L Browning
Dec 15, 2010·Biochemical and Biophysical Research Communications·Sayyed R MousaviMajid Talebi
Feb 12, 2011·American Journal of Human Genetics·Brian L Browning, Sharon R Browning
Jun 1, 1984·IEEE Transactions on Pattern Analysis and Machine Intelligence·S Geman, D Geman
Jun 16, 2012·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Derek Aguiar, Sorin Istrail
Jan 11, 2013·BMC Systems Biology·Minzhu XieTao Jiang
Jun 21, 2013·Bioinformatics·Zhi-Zhong ChenLusheng Wang
Mar 29, 2014·PLoS Computational Biology·Emily BergerBonnie Berger
Feb 7, 2015·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Murray PattersonAlexander Schönhuth

❮ Previous
Next ❯

Citations

Sep 26, 2019·FEMS Yeast Research·Arthur R Gorter de VriesJean-Marc G Daran
Feb 26, 2020·Biology Letters·Patrick Monnahan, Yaniv Brandvain
Jun 20, 2020·BMC Bioinformatics·Sina MajidianDick de Ridder
Sep 22, 2020·Genome Biology·Sven D SchrinnerGunnar W Klau
Oct 30, 2020·The Plant Journal : for Cell and Molecular Biology·Weiyi ZhangWeiwei Wen
Jan 15, 2021·Bioinformatics·Samuel M NichollsAmanda Clare
Dec 24, 2018·G3 : Genes - Genomes - Genetics·María L ZingarettiMiguel Pérez-Enciso
May 1, 2021·Genome Biology·Omar Abou SaadaJoseph Schacherer

❮ Previous
Next ❯

Software Mentioned

Mason
WhatsHap
SDhaP
PoPG
Hapcompass
Poly
Harsh
HapTree
HapAssembly
HASH

Related Concepts

Trending Feeds

COVID-19

Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Blastomycosis

Blastomycosis fungal infections spread through inhaling Blastomyces dermatitidis spores. Discover the latest research on blastomycosis fungal infections here.

Nuclear Pore Complex in ALS/FTD

Alterations in nucleocytoplasmic transport, controlled by the nuclear pore complex, may be involved in the pathomechanism underlying multiple neurodegenerative diseases including Amyotrophic Lateral Sclerosis and Frontotemporal Dementia. Here is the latest research on the nuclear pore complex in ALS and FTD.

Applications of Molecular Barcoding

The concept of molecular barcoding is that each original DNA or RNA molecule is attached to a unique sequence barcode. Sequence reads having different barcodes represent different original molecules, while sequence reads having the same barcode are results of PCR duplication from one original molecule. Discover the latest research on molecular barcoding here.

Chronic Fatigue Syndrome

Chronic fatigue syndrome is a disease characterized by unexplained disabling fatigue; the pathology of which is incompletely understood. Discover the latest research on chronic fatigue syndrome here.

Evolution of Pluripotency

Pluripotency refers to the ability of a cell to develop into three primary germ cell layers of the embryo. This feed focuses on the mechanisms that underlie the evolution of pluripotency. Here is the latest research.

Position Effect Variegation

Position Effect Variagation occurs when a gene is inactivated due to its positioning near heterochromatic regions within a chromosome. Discover the latest research on Position Effect Variagation here.

STING Receptor Agonists

Stimulator of IFN genes (STING) are a group of transmembrane proteins that are involved in the induction of type I interferon that is important in the innate immune response. The stimulation of STING has been an active area of research in the treatment of cancer and infectious diseases. Here is the latest research on STING receptor agonists.

Microbicide

Microbicides are products that can be applied to vaginal or rectal mucosal surfaces with the goal of preventing, or at least significantly reducing, the transmission of sexually transmitted infections. Here is the latest research on microbicides.