Linearization of genome sequence graphs revisited.
Ontology highlight
ABSTRACT:
SUBMITTER: Lisiecka A
PROVIDER: S-EPMC8264155 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:BackgroundGenotyping of sequence variants typically involves, as a first step, the alignment of sequencing reads to a linear reference genome. Because a linear reference genome represents only a small fraction of all the DNA sequence variation within a species, reference allele bias may occur at highly polymorphic or divergent regions of the genome. Graph-based methods facilitate the comparison of sequencing reads to a variation-aware genome graph, which incorporates a collection of non-redundant DNA sequences that segregate within a species. We compared the accuracy and sensitivity of graph-based sequence variant genotyping using the Graphtyper software to two widely-used methods, i.e., GATK and SAMtools, which rely on linear reference genomes using whole-genome sequencing data from 49 Original Braunvieh cattle.ResultsWe discovered 21,140,196, 20,262,913, and 20,668,459 polymorphic sites using GATK, Graphtyper, and SAMtools, respectively. Comparisons between sequence variant genotypes and microarray-derived genotypes showed that Graphtyper outperformed both GATK and SAMtools in terms of genotype concordance, non-reference sensitivity, and non-reference discrepancy. The sequence variant genotypes that were obtained using Graphtyper had the smallest number of Mendelian inconsistencies between sequence-derived single nucleotide polymorphisms and indels in nine sire-son pairs. Genotype phasing and imputation using the Beagle software improved the quality of the sequence variant genotypes for all the tools evaluated, particularly for animals that were sequenced at low coverage. Following imputation, the concordance between sequence- and microarray-derived genotypes was almost identical for the three methods evaluated, i.e., 99.32, 99.46, and 99.24% for GATK, Graphtyper, and SAMtools, respectively. Variant filtration based on commonly used criteria improved genotype concordance slightly but it also decreased sensitivity. Graphtyper required considerably more computing resources than SAMtools but less than GATK.ConclusionsSequence variant genotyping using Graphtyper is accurate, sensitive and computationally feasible in cattle. Graph-based methods enable sequence variant genotyping from variation-aware reference genomes that may incorporate cohort-specific sequence variants, which is not possible with the current implementation of state-of-the-art methods that rely on linear reference genomes.
| S-EPMC6521551 | biostudies-literature
Project description:Cultivated tomato (Solanum lycopersicum L.) is the second most important vegetable crop after potato and a member of thirteen interfertile species of Solanum genus. Domestication and continuous selection for desirable traits made cultivated tomato species susceptible to many stresses as compared to the wild species. In this study, we analyzed and compared the genomes of wild and cultivated tomato accessions to identify the genomic regions that encountered changes during domestication.Analysis was based on SNP and InDel mining of twentynine accessions of twelve wild tomato species and forty accessions of cultivated tomato. Percentage of common SNPs among the accessions within a species corresponded with the reproductive behavior of the species. SNP profiles of the wild tomato species within a phylogenetic subsection varied with their geographical distribution. Interestingly, the ratio of genic SNP to total SNPs increased with phylogenetic distance of the wild tomato species from the domesticated species, suggesting that variations in gene-coding region play a major role in speciation. We retrieved 2439 physical positions in 1594 genes including 32 resistance related genes where all the wild accessions possessed a common wild variant allele different from all the cultivated accessions studied. Tajima's D analysis predicted a very strong purifying selection associated with domestication in nearly 1% of its genome, half of which is contributed by chromosome 11. This genomic region with a low Tajima's D value hosts a variety of genes associated with important agronomic trait such as, fruit size, tiller number and wax deposition.Our analysis revealed a broad-spectrum genetic base in wild tomato species and erosion of that in cultivated tomato due to recurrent selection for agronomically important traits. Identification of the common wild variant alleles and the genomic regions undergoing purifying selection during cultivation would facilitate future breeding program by introgression from wild species.
| S-EPMC5455116 | biostudies-literature
Project description:Bacillus pumilus strain SAFR-032 is a non-pathogenic spore-forming bacterium exhibiting an anomalously high persistence in bactericidal environments. In its dormant state, it is capable of withstanding doses of ultraviolet (UV) radiation or hydrogen peroxide, which are lethal for the vast majority of microorganisms. This unusual resistance profile has made SAFR-032 a reference strain for studies of bacterial spore resistance. The complete genome sequence of B. pumilus SAFR-032 was published in 2007 early in the genomics era. Since then, the SAFR-032 strain has frequently been used as a source of genetic/genomic information that was regarded as representative of the entire B. pumilus species group. Recently, our ongoing studies of conservation of gene distribution patterns in the complete genomes of various B. pumilus strains revealed indications of misassembly in the B. pumilus SAFR-032 genome. Synteny-driven local genome resequencing confirmed that the original SAFR-032 sequence contained assembly errors associated with long sequence repeats. The genome sequence was corrected according to the new findings. In addition, a significantly improved annotation is now available. Gene orders were compared and portions of the genome arrangement were found to be similar in a wide spectrum of Bacillus strains.
| S-EPMC4924849 | biostudies-other
Project description:Many studies investigating Mycobacterium avium subsp. paratuberculosis in Crohn's disease have used molecular detection of IS900 in clinical samples, but some have described polymorphisms in IS900 as variants of this organism. Analysis of 23 M. avium subsp. paratuberculosis isolates revealed that IS900 is highly conserved, with only two sequevars distinguishing sheep and cattle lineages. Amplification of IS900-like sequences is not sufficient as a proxy for M. avium subsp. paratuberculosis.
| S-EPMC1393169 | biostudies-literature
Project description:We have exhaustively enumerated all simple, connected graphs of a finite order and have computed a selection of invariants over this set. Integer sequences were constructed from these invariants and checked against the Online Encyclopedia of Integer Sequences (OEIS). 141 new sequences were added and six sequences were extended. From the graph database, we were able to programmatically suggest relationships among the invariants. It will be shown that we can readily visualize any sequence of graphs with a given criteria. The code has been released as an open-source framework for further analysis and the database was constructed to be extensible to invariants not considered in this work.
| S-EPMC4809059 | biostudies-literature
Project description:BACKGROUND:In order to find correlated pairs of positions between proteins, which are useful in predicting interactions, it is necessary to concatenate two large multiple sequence alignments such that the sequences that are joined together belong to those that interact in their species of origin. When each protein is unique then the species name is sufficient to guide this match, however, when there are multiple related sequences (paralogs) in each species then the pairing is more difficult. In bacteria a good guide can be gained from genome co-location as interacting proteins tend to be in a common operon but in eukaryotes this simple principle is not sufficient. RESULTS:The methods developed in this paper take sets of paralogs for different proteins found in the same species and make a pairing based on their evolutionary distance relative to a set of other proteins that are unique and so have a known relationship (singletons). The former constitute a set of unlabelled nodes in a graph while the latter are labelled. Two variants were tested, one based on a phylogenetic tree of the sequences (the topology-based method) and a simpler, faster variant based only on the inter-sequence distances (the distance-based method). Over a set of test proteins, both gave good results, with the topology method performing slightly better. CONCLUSIONS:The methods develop here still need refinement and augmentation from constraints other than the sequence data alone, such as known interactions from annotation and databases, or non-trivial relationships in genome location. With the ever growing numbers of eukaryotic genomes, it is hoped that the methods described here will open a route to the use of these data equal to the current success attained with bacterial sequences.
| S-EPMC5613400 | biostudies-literature
Project description:AIMS:Mitofusin (Mfn)2 redundantly promotes mitochondrial outer membrane tethering and organelle fusion with Mfn1, and uniquely functions as the mitochondrial receptor for Parkin during PTEN-induced putative kinase 1 (PINK1)-Parkin-mediated mitophagy. Selective deletion of Mfn2 with retention of Mfn1 preserves mitochondrial fusion while rendering damaged mitochondria resistant to normal quality control culling mechanisms. Consequently, neuron and cardiomyocyte-specific Mfn2 gene ablation is associated with accumulation of damaged mitochondria and organ dysfunction. Here, we determined how mitochondrial DNA (mtDNA) damage contributes to cardiomyopathy in Mfn2-deficient hearts. RESULTS:RNA sequencing of Mfn2-deficient hearts revealed increased expression of some nuclear-encoded mitochondrial genes, but mitochondrial-encoded transcripts were not upregulated in parallel and mtDNA content was decreased. Ultra-deep sequencing of mtDNA showed no increase in single nucleotide mutations, but copy number variations representing insertion-deletion (in-del) mutations were induced over time by cardiomyocyte-specific Mfn2 deficiency. Double-strand mtDNA breaks in the form of in-dels were confirmed by polymerase chain reaction, and in the form of linear mitochondrial genomes were identified by southern blot analysis. Linearization of Drosophila cardiomyocyte mtDNA using conditional cardiomyocyte-specific expression of mitochondrial targeted XhoI recapitulated the cardiomyopathy of Mfn2-deficient mouse hearts. INNOVATION:This is the first description of mitochondrial genome linearization as a causative factor in cardiomyopathy. CONCLUSION:One of the consequences of interrupting mitochondrial culling by the PINK1-Mfn2-Parkin mechanism is an increase in mtDNA double-stranded breaks, which adversely impact mitochondrial function and DNA replication.
| S-EPMC4208594 | biostudies-literature
Project description:Deep sequencing has enabled the investigation of a wide range of environmental microbial ecosystems, but the high memory requirements for de novo assembly of short-read shotgun sequencing data from these complex populations are an increasingly large practical barrier. Here we introduce a memory-efficient graph representation with which we can analyze the k-mer connectivity of metagenomic samples. The graph representation is based on a probabilistic data structure, a Bloom filter, that allows us to efficiently store assembly graphs in as little as 4 bits per k-mer, albeit inexactly. We show that this data structure accurately represents DNA assembly graphs in low memory. We apply this data structure to the problem of partitioning assembly graphs into components as a prelude to assembly, and show that this reduces the overall memory requirements for de novo assembly of metagenomes. On one soil metagenome assembly, this approach achieves a nearly 40-fold decrease in the maximum memory requirements for assembly. This probabilistic graph representation is a significant theoretical advance in storing assembly graphs and also yields immediate leverage on metagenomic assembly.
| S-EPMC3421212 | biostudies-literature
Project description:The complex correlation structure of a collection of orthologous DNA sequences is uniquely captured by the "ancestral recombination graph" (ARG), a complete record of coalescence and recombination events in the history of the sample. However, existing methods for ARG inference are computationally intensive, highly approximate, or limited to small numbers of sequences, and, as a consequence, explicit ARG inference is rarely used in applied population genomics. Here, we introduce a new algorithm for ARG inference that is efficient enough to apply to dozens of complete mammalian genomes. The key idea of our approach is to sample an ARG of [Formula: see text] chromosomes conditional on an ARG of [Formula: see text] chromosomes, an operation we call "threading." Using techniques based on hidden Markov models, we can perform this threading operation exactly, up to the assumptions of the sequentially Markov coalescent and a discretization of time. An extension allows for threading of subtrees instead of individual sequences. Repeated application of these threading operations results in highly efficient Markov chain Monte Carlo samplers for ARGs. We have implemented these methods in a computer program called ARGweaver. Experiments with simulated data indicate that ARGweaver converges rapidly to the posterior distribution over ARGs and is effective in recovering various features of the ARG for dozens of sequences generated under realistic parameters for human populations. In applications of ARGweaver to 54 human genome sequences from Complete Genomics, we find clear signatures of natural selection, including regions of unusually ancient ancestry associated with balancing selection and reductions in allele age in sites under directional selection. The patterns we observe near protein-coding genes are consistent with a primary influence from background selection rather than hitchhiking, although we cannot rule out a contribution from recurrent selective sweeps.
| S-EPMC4022496 | biostudies-literature
Project description:MotivationThe size of a genome graph-the space required to store the nodes, node labels and edges-affects the efficiency of operations performed on it. For example, the time complexity to align a sequence to a graph without a graph index depends on the total number of characters in the node labels and the number of edges in the graph. This raises the need for approaches to construct space-efficient genome graphs.ResultsWe point out similarities in the string encoding mechanisms of genome graphs and the external pointer macro (EPM) compression model. We present a pair of linear-time algorithms that transform between genome graphs and EPM-compressed forms. The algorithms result in an upper bound on the size of the genome graph constructed in terms of an optimal EPM compression. To further reduce the size of the genome graph, we propose the source assignment problem that optimizes over the equivalent choices during compression and introduce an ILP formulation that solves that problem optimally. As a proof-of-concept, we introduce RLZ-Graph, a genome graph constructed based on the relative Lempel-Ziv algorithm. Using RLZ-Graph, across all human chromosomes, we are able to reduce the disk space to store a genome graph on average by 40.7% compared to colored compacted de Bruijn graphs constructed by Bifrost under the default settings. The RLZ-Graph scales well in terms of running time and graph sizes with an increasing number of human genome sequences compared to Bifrost and variation graphs produced by VGtoolkit.AvailabilityThe RLZ-Graph software is available at: https://github.com/Kingsford-Group/rlzgraph.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC8275343 | biostudies-literature