MegaPath: Low-Similarity Pathogen Detection from Metagenomic NGS Data

Abstract

Detecting pathogen, the causal bacteria or virus, of infections such as pneumonia is an important step in diagnosis. Traditional method for pathogen detection is time- consuming as infectious disease may be caused by a large range of pathogens which should be checked one by one. This causes the delay of treatment or even mistreatment of patients. Unbiased next-generation sequencing (NGS) can detect DNA fragments (reads) of all species in a metagenomics sample with a mixture of different species. Those NGS reads could be classified into different taxa by comparing them with a collection of reference genome sequences, and pathogens could be detected if some reads match them. In clinical diagnoses, it is important that a classifier can detect a significant number of reads supporting the potential pathogens and report as few false classifications as possible, to give a high abundance rank for the pathogen. Otherwise, the pathogen cannot be distinguished from background noises, and it will take doctors a long time to go through a long list of candidates to verify its existence. Existing metagenomic classifiers do not perform well for detecting low-similarity pathogens, i.e., pathogen with genome that is not similar to the reference. It is because most classifiers detect pathogen by constructing a characteristic profile (e.g. k-mers) for each reference and assign reads to species by comparing them with the profiles. When the characteristic profile does not match with the genome of low- similarity pathogens, this approach fails and results in many incorrect or nonspecifically classification. Some tools assign reads to reference sequences by local or semi-global alignment. The analysis time is long (over 4 hours for a typical dataset of 1 Gb) but more reads from the pathogen can be assigned correctly. However, the alignment score of reads are still low for low-similarity pathogen. These reads cannot be assigned to the pathogen specifically such that the number of reads supporting the pathogen is still too low. In order to detect low-similarity pathogen, we introduce MegaPath for NGS-based pathogen detection. There are two major contributions. First, instead of assigning each read to reference sequence one by one, MegaPath analyzes all aligned reads globally to determine a subset of reads with confident alignments. Then MegaPath reassigns non-specifically aligned reads to species with confident alignments, and discards unconfident alignments to avoid potential false classifications. It will increase the number of reads supporting the pathogen and reduce the number of false positive assignments. Second, MegaPath adopts a fast alignment-based approach using an enhanced maximum-exact-match prefix seeding strategy and SIMD-accelerated Smith-Waterman algorithm. Use a metagenomic NGS sample of cerebrospinal fluid (CSF) [1] as an example. The similarity of the pathogen to reference is 18.7%. Centrifuge [2] and Kraken [4], based on characteristic profile, detect 31 and 6 reads from the pathogen respectively. The abundance rank of the pathogen is 710 and 384 respectively. Thus, the doctor needs to go through a list of 300+ species to find out the pathogen. By an alignment processes taking 4 hours, SURPI [3] can detect 76 reads for the pathogen and its rank go up to 245. With better alignment tools and global analysis of reads, MegaPath takes less than one hour to detect 608 reads for the pathogen and its rank is at 33. Thus, MegaPath has the best performance among existing software with a reasonable running time. Experiment results for more datasets can be found in the full paper. In addition to detecting pathogens with known reference sequences, MegaPath can also detect pathogens without any similar DNA-level sequences in the reference database, using de novo assembly and protein alignment.