Dataset Information

Compact and evenly distributed k-mer binning for genomic sequences.

ABSTRACT:

Motivation

The processing of k-mers (subsequences of length k) is at the foundation of many sequence processing algorithms in bioinformatics, including k-mer counting for genome size estimation, genome assembly, and taxonomic classification for metagenomics. Minimizers-ordered m-mers where m < k - are often used to group k-mers into bins as a first step in such processing. However, minimizers are known to generate bins of very different sizes, which can pose challenges for distributed and parallel processing, as well as generally increase memory requirements. Furthermore, although various minimizer orderings have been proposed, their practical value for improving tool efficiency has not yet been fully explored.

Results

We present Discount, a distributed k-mer counting tool based on Apache Spark, which we use to investigate the behaviour of various minimizer orderings in practice when applied to metagenomics data. Using this tool, we then introduce the universal frequency ordering, a new combination of frequencysampled minimizers and universal k-mer hitting sets, which yields both evenly distributed binning and small bin sizes. We show that this ordering allows Discount to perform distributed k-mer counting on a large dataset in as little as 1/8 of the memory of comparable approaches, making it the most efficient out-of-core distributed k-mer counting method available.

Availability

Discount is GPL licensed and available at https://github.com/jtnystrom/discount.

Supplementary information

Supplementary data are available at Bioinformatics online.

SUBMITTER: Nystrom-Persson J

PROVIDER: S-EPMC8428581 | biostudies-literature |

REPOSITORIES: biostudies-literature

ACCESS DATA

Similar Datasets

Project description:Background. A large proportion of natural grasslands around the world is exposed to overgrazing resulting in land degradation and biodiversity loss. Although there is an increasing effort in the promotion of sustainable livestock management, rangeland degradation still occurs because animals' foraging behaviour is highly selective at different spatial scales. The assessment of the ecological mechanisms modulating the spatial distribution of grazing and how to control it has critical implications for long term conservation of resources and the sustainability of livestock production. Considering the relevance of social interactions on animals' space use patterns, our aim was to explore the potential effects of including animals' social context into management strategies using domestic sheep grazing in rangelands as case study. Methods. We used GPS data from 19 Merino sheep (approximately 10% of the flock) grazing on three different paddocks (with sizes from 80 to 1000 Ha) during a year, to estimate resource selection functions of sheep grazing in flocks of different levels of heterogeneity. We assessed the effects of sheep class (i.e., ewes, wethers, and hoggets), age, body condition and time since release on habitat selection patterns. Results. We found that social rank was reflected on sheep habitat use, where dominant individuals (i.e., reproductive females) used more intensively the most preferred areas and low-ranked (i.e., yearlings) used less preferred areas. Our results showed that when sheep grazed on more heterogeneous flocks, grazing patterns were more evenly distributed at all the paddocks considered in this study. On the other hand, when high-ranked individuals were removed from the flock, low-ranked sheep shifted their selection patterns by increasing the use of the most preferred areas and strongly avoided to use less preferred sites (i.e., a highly selective grazing behaviour). Discussion. Although homogenization and segregation of flocks by classes are common practices to increase flock productivity, we are proposing an alternative that employs behavioural interactions in heterogeneous flocks to generate more evenly distributed grazing patterns. This practice can be combined with other practices such as rotational grazing and guardian dogs (to decrease mortality levels that may be generated by sheep grazing on more risky habitats). This does not imply any modifications of livestock stocking rates and densities or any additional investments for labour and materials. Considering livestock behaviour is critical for the design of sustainable management practices that balance landscape conservation and livestock productivity.

Project description:BackgroundIn metagenomic studies, a process called binning is necessary to assign contigs that belong to multiple species to their respective phylogenetic groups. Most of the current methods of binning, such as BLAST, k-mer and PhyloPythia, involve assigning sequence fragments by comparing sequence similarity or sequence composition with already-sequenced genomes that are still far from comprehensive. We propose a semi-supervised seeding method for binning that does not depend on knowledge of completed genomes. Instead, it extracts the flanking sequences of highly conserved 16S rRNA from the metagenome and uses them as seeds (labels) to assign other reads based on their compositional similarity.ResultsThe proposed seeding method is implemented on an unsupervised Growing Self-Organising Map (GSOM), and called Seeded GSOM (S-GSOM). We compared it with four well-known semi-supervised learning methods in a preliminary test, separating random-length prokaryotic sequence fragments sampled from the NCBI genome database. We identified the flanking sequences of the highly conserved 16S rRNA as suitable seeds that could be used to group the sequence fragments according to their species. S-GSOM showed superior performance compared to the semi-supervised methods tested. Additionally, S-GSOM may also be used to visually identify some species that do not have seeds. The proposed method was then applied to simulated metagenomic datasets using two different confidence threshold settings and compared with PhyloPythia, k-mer and BLAST. At the reference taxonomic level Order, S-GSOM outperformed all k-mer and BLAST results and showed comparable results with PhyloPythia for each of the corresponding confidence settings, where S-GSOM performed better than PhyloPythia in the >/= 10 reads datasets and comparable in the > or = 8 kb benchmark tests.ConclusionIn the task of binning using semi-supervised learning methods, results indicate S-GSOM to be the best of the methods tested. Most importantly, the proposed method does not require knowledge from known genomes and uses only very few labels (one per species is sufficient in most cases), which are extracted from the metagenome itself. These advantages make it a very attractive binning method. S-GSOM outperformed the binning methods that depend on already-sequenced genomes, and compares well to the current most advanced binning method, PhyloPythia.