Rapid and precise alignment of raw reads against redundant databases with KMA.
Clausen PTLC, Aarestrup FM, Lund O. · 2018
Read Rapid and precise alignment of raw reads against redundant databases with KMA. by Clausen PTLC, Aarestrup FM, Lund O. (2018) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc6116485.txt.
Introduction
Clausen and co-authors present a methods article in BMC Bioinformatics on a fast tool for mapping DNA reads. Clinics now use DNA sequencing to find germs and drug resistance. That work needs reads matched against databases full of near-duplicate entries. Older tools can be slow or pick the wrong match.
The tool, called KMA, matches raw reads straight against such databases. It uses short word-like seeds to speed the search. A classic alignment method then refines each match. Tests used fake data and E. coli reads. The authors report that KMA beat six rival tools on speed and accuracy. Memory use stayed about the same.
Catalog record
| CREATOR | Clausen PTLC, Aarestrup FM, Lund O. |
|---|---|
| YEAR | 2018 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| LICENSE | CC BY 4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rapid and precise alignment of raw reads against redundant databases with KMA By Philip T. L. C. Clausen, Frank M. Aarestrup, Ole Lund Published in: BMC Bioinformatics DOI: 10.1186/s12859-018-2336-6 ABSTRACT Background As the cost of sequencing has declined, clinical diagnostics based on next generation sequencing (NGS) have become reality. Diagnostics based on sequencing will require rapid and precise mapping against redundant databases because some of the most important determinants, such as antimicrobial resistance and core genome multilocus sequence typing (MLST) alleles, are highly similar to one another. In order to facilitate this, a novel mapping method, KMA (k-mer alignment), was designed. KMA is able to map raw reads directly against redundant databases, it also scales well for large redundant databases. KMA uses k-mer seeding to speed up mapping and the Needleman-Wunsch algorithm to accurately align extensions from k-mer seeds. Multi-mapping reads are resolved using a novel sorting scheme (ConClave scheme), ensuring an accurate selection of templates. Results The functionality of KMA was compared with SRST2, MGmapper, BWA-MEM, Bowtie2, Minimap2 and Salmon, using both simulated data and a dataset of Escherichia coli mapped against resistance genes and core genome MLST alleles. KMA outperforms current methods with respect to both accuracy and speed, while using a comparable amount of memory. Conclusion With KMA, it was possible map raw reads directly against redundant databases with high accuracy, speed and memory efficiency. Electronic supplementary material The online version of this article (10.1186/s12859-018-2336-6) contains supplementary material, which is available to authorized users. BACKGROUND In bioinformatics, the oldest and probably the single most important tool is the alignment of one or more sequences. Alignments informs us how similar a sequence is compared with another sequence and can be used to quantify the abundance of any similar sequence pattern. If the found pattern has an annotation, this can be transferred to the query sequence. The proper choice of alignment method is thus critical for the further investigations [1]. Over the past decade several mapping methods have been developed that enable direct mapping of raw reads against target sequences. Previous studies have shown read-mapping based approaches to be superior to the more traditional methods where the reads are first assembled, and the assembly is hereafter BLAST’ed. against a database. The success of such methods are highly dictated by the quality of the assembly, because BLAST remains too slow to map the raw reads directly. Which is problematic within repeat and low depth regions of the genome, where the assembly often results in gaps between the assembled contigs, leading to missing data [2, 3]. Today Bowtie2 [4], BWA-MEM [5] and Minimap2 [6] are popular mapping methods that allows for fast mapping and alignment of raw reads against large reference genomes. All of these methods can be adapted to map against entire databases of sequences, but suffer from random selection when there is a tie for best match. In order to resolve these ties, several tools have been designed to resolve these random selections with extensive pre- and post-processing. Examples of these are SRST2 [3] and MGmapper [7] which both pre- and post-process the sequences for mapping with Bowtie2 and BWA-MEM, respectively. Other methods, such as Salmon [8], uses the EM algorithm in order to estimate the sequencing level of homologous templates from mappings generated by traditional methods. The redundant databases used in genomic epidemiology are however still posing a challenge regarding mapping raw reads directly. When databases are constantly updated with new sequences due to natural evolution, the results are in a constantly changing state, making clustering difficult. This feature of the databases makes direct mapping of raw reads troublesome, as there is no guarantee that the read will cover a unique part of a reference sequence, resulting in a tie for best match. Redundancy is a problem when mapping to bacterial databases, but to a lesser degree since these databases are not as redundant as some of the gene databases, and better use can be made of paired end reads since only one of the ends will often map to single genes. There is a need for new methods to resolve the issue with redundancy in an accurate and fast manner so that acute decisions can be made. In response to this need, a new alignment method, KMA (k-mer alignment), was developed. KMA introduces a novel sorting scheme, ConClave, in order to distinguish homologous templates. METHODS We introduce a novel alignment method, KMA, and scoring scheme, ConClave, which allows for mapping of raw reads directly against redundant databases. KMA diverges from known mappers by allowing redundancy within the databases, and KMA also produces consensus sequences and a result overview. KMA was created to be as intuitive and user friendly as possible, based on our current user demands and analysis challenges. In order to solve this, KMA works in five main steps: trimming of reads, heuristic k-mer mapping, fine alignment, ConClave scoring and reference assembly (see Fig. 1).Fig. 1Overview of step 1–4 of the KMA algorithm. 1: trim reads. 2. Match k-mers between query and database. 3a: Extend matching k-mer seeds, and identify regions with mismatches. 3b: Use the Needleman-Wunsch algorithm to align regions of mismatching k-mers. 4: Conclave scoring used to choose one best-aligning template per query sequence. Heuristic k-mer mapping When mapping against databases, a query sequence can fall within two categories: the query does not look like anything in the database or the query looks like something in the database. Depending on the database, it is therefore necessary to determine at an early stage whether alignment of a given sequence is feasible or if the sequence should be discarded from further analysis. Computationally, it is much faster to map raw reads against template sequences and determine their approximate origin than it is to perform alignment giving the exact differences between sequences. In order to exploit this, KMA maps k-mers between the query sequence and template database. The matching k-mers are then used to produce a mapping score where a matching k-mer is rewarded with a score of k while k-mer mismatches are penalized with − 1. For a query sequence to be accepted for alignment, it must have a positive score based on this mapping, equivalent to a minimum identity of (k + 1)− 1 in k-mer space. In the case where a query sequence is accepted, the potential template candidates are limited by linking the matching k-mers to their respective template sequences. Fine alignment KMA uses a hash map of indexed k-mers from which to start alignment, where this indexing is computed for templates passing the heuristic k-mer mapping. The indexed k-mers are then used as seeds from which to start alignment, where each matching seed is extended to give an optimal score. To enable a high resolution of gaps and mismatches, KMA utilizes the Needleman-Wunsch algorithm [9] to align the pieces of query and template sequence between seed-extends. The tails of the alignment, before the first seed and after the last, are aligned with a specialized version of the Needleman-Wunsch algorithm allowing for early stopping so that leading and trailing gaps can be skipped. ConClave scoring As KMA is designed to map sequences against redundant databases, the possibility of a tie for best matching