Dataset Information

ComHapDet: a spatial community detection algorithm for haplotype assembly.

ABSTRACT:

Background

Haplotypes, the ordered lists of single nucleotide variations that distinguish chromosomal sequences from their homologous pairs, may reveal an individual's susceptibility to hereditary and complex diseases and affect how our bodies respond to therapeutic drugs. Reconstructing haplotypes of an individual from short sequencing reads is an NP-hard problem that becomes even more challenging in the case of polyploids. While increasing lengths of sequencing reads and insert sizes helps improve accuracy of reconstruction, it also exacerbates computational complexity of the haplotype assembly task. This has motivated the pursuit of algorithmic frameworks capable of accurate yet efficient assembly of haplotypes from high-throughput sequencing data.

Results

We propose a novel graphical representation of sequencing reads and pose the haplotype assembly problem as an instance of community detection on a spatial random graph. To this end, we construct a graph where each read is a node with an unknown community label associating the read with the haplotype it samples. Haplotype reconstruction can then be thought of as a two-step procedure: first, one recovers the community labels on the nodes (i.e., the reads), and then uses the estimated labels to assemble the haplotypes. Based on this observation, we propose ComHapDet - a novel assembly algorithm for diploid and ployploid haplotypes which allows both bialleleic and multi-allelic variants.

Conclusions

Performance of the proposed algorithm is benchmarked on simulated as well as experimental data obtained by sequencing Chromosome 5 of tetraploid biallelic Solanum-Tuberosum (Potato). The results demonstrate the efficacy of the proposed method and that it compares favorably with the existing techniques.

SUBMITTER: Sankararaman A

PROVIDER: S-EPMC7488034 | biostudies-literature | 2020 Sep

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

ComHapDet: a spatial community detection algorithm for haplotype assembly.

Sankararaman Abishek A Vikalo Haris H Baccelli François F

BMC genomics 20200909 Suppl 9

<h4>Background</h4>Haplotypes, the ordered lists of single nucleotide variations that distinguish chromosomal sequences from their homologous pairs, may reveal an individual's susceptibility to hereditary and complex diseases and affect how our bodies respond to therapeutic drugs. Reconstructing haplotypes of an individual from short sequencing reads is an NP-hard problem that becomes even more challenging in the case of polyploids. While increasing lengths of sequencing reads and insert sizes h ...[more]

PMID: 32900369

Similar Datasets

Project description:BackgroundIn diploid organisms, whole-genome haplotype assembly relies on the accurate identification and assignment of heterozygous single-nucleotide polymorphism alleles to the correct homologous chromosomes. This appropriate phasing of these alleles ensures that combinations of single-nucleotide polymorphisms on any chromosome, called haplotypes, can then be used in downstream genetic analysis approaches including determining their potential association with important phenotypic traits. A number of statistical algorithms and complementary computational software tools have been developed for whole-genome haplotype construction from genomic sequence data. However, many algorithms lack the ability to phase long haplotype blocks and simultaneously achieve a competitive accuracy.ResultsIn this research we present HaploMaker, a novel reference-based haplotype assembly algorithm capable of accurately and efficiently phasing long haplotypes using paired-end short reads and longer Pacific Biosciences reads from diploid genomic sequences. To achieve this we frame the problem as a directed acyclic graph with edges weighted on read evidence and use efficient path traversal and minimization techniques to optimally phase haplotypes. We compared the HaploMaker algorithm with 3 other common reference-based haplotype assembly tools using public haplotype data of human individuals from the Platinum Genome project. With short-read sequences, the HaploMaker algorithm maintained a competitively low switch error rate across all haplotype lengths and was superior in phasing longer genomic regions. For longer Pacific Biosciences reads, the phasing accuracy of HaploMaker remained competitive for all block lengths and generated substantially longer block lengths than the competing algorithms.ConclusionsHaploMaker provides an improved haplotype assembly algorithm for diploid genomic sequences by accurately phasing longer haplotypes. The computationally efficient and portable nature of the Java implementation of the algorithm will ensure that it has maximal impact in reference-sequence-based haplotype assembly applications.

Project description:Background and aimsThere is a paucity of empirical research and a lack of predictive models concerning the interplay between spatial scale and disturbance as they affect the structure and assembly of plant communities. We proposed and tested a trait dispersion-based conceptual model hypothesizing that disturbance reinforces assembly processes differentially across spatial scales. Disturbance would reinforce functional divergence at the small scale (neighbourhood), would not affect functional dispersion at the intermediate scale (patch) and would reinforce functional convergence at the large scale (site). We also evaluated functional and species richness of native and exotic plants to infer underlying processes. Native and exotic species richness were expected to increase and decrease with disturbance, respectively, at the neighbourhood scale, and to show similar associations with disturbance at the patch (concave) and site (negative) scales.MethodsIn an arid shrubland, we estimated species richness and functional dispersion and richness within 1 m2 quadrats (neighbourhood) nested within 100 m2 plots (patch) along a small-scale natural disturbance gradient caused by an endemic fossorial rodent. Data for the site scale (2500 m2 plots) were taken from a previous study. We also tested the conceptual model through a quantitative literature review and a meta-analysis.Key resultsAs spatial scale increased, disturbance sequentially promoted functional divergence, random trait dispersion and functional convergence. Functional richness was unaffected by disturbance across spatial scales. Disturbance favoured natives over exotics at the neighbourhood scale, while both decreased under high disturbance at the patch and site scales.ConclusionsThe results supported the hypothesis that disturbance reinforces assembly processes differentially across scales and hampers plant invasion. The quantitative literature review and the meta-analysis supported most of the model predictions.

Project description:BackgroundIdentification of transcription factor binding sites (also called 'motif discovery') in DNA sequences is a basic step in understanding genetic regulation. Although many successful programs have been developed, the problem is far from being solved on account of diversity in gene expression/regulation and the low specificity of binding sites. State-of-the-art algorithms have their own constraints (e.g., high time or space complexity for finding long motifs, low precision in identification of weak motifs, or the OOPS constraint: one occurrence of the motif instance per sequence) which limit their scope of application.ResultsIn this paper, we present a novel and fast algorithm we call TFBSGroup. It is based on community detection from a graph and is used to discover long and weak (l,d) motifs under the ZOMOPS constraint (zero, one or multiple occurrence(s) of the motif instance(s) per sequence), where l is the length of a motif and d is the maximum number of mutations between a motif instance and the motif itself. Firstly, TFBSGroup transforms the (l, d) motif search in sequences to focus on the discovery of dense subgraphs within a graph. It identifies these subgraphs using a fast community detection method for obtaining coarse-grained candidate motifs. Next, it greedily refines these candidate motifs towards the true motif within their own communities. Empirical studies on synthetic (l, d) samples have shown that TFBSGroup is very efficient (e.g., it can find true (18, 6), (24, 8) motifs within 30 seconds). More importantly, the algorithm has succeeded in rapidly identifying motifs in a large data set of prokaryotic promoters generated from the Escherichia coli database RegulonDB. The algorithm has also accurately identified motifs in ChIP-seq data sets for 12 mouse transcription factors involved in ES cell pluripotency and self-renewal.ConclusionsOur novel heuristic algorithm, TFBSGroup, is able to quickly identify nearly exact matches for long and weak (l, d) motifs in DNA sequences under the ZOMOPS constraint. It is also capable of finding motifs in real applications. The source code for TFBSGroup can be obtained from http://bioinformatics.bioengr.uic.edu/TFBSGroup/.

Dataset Information

ComHapDet: a spatial community detection algorithm for haplotype assembly.

Background

Results

Conclusions

Publications

ComHapDet: a spatial community detection algorithm for haplotype assembly.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets