Distance-based phylogenetic inference from typing data: a unifying view.

Typing methods are widely used in the surveillance of infectious diseases, outbreaks investigation and studies of the natural history of an infection. Moreover, their use is becoming standard, in particular with the introduction of high-throughput sequencing. On the other hand, the data being generated are massive and many algorithms have been proposed for a phylogenetic analysis of typing data, addressing both correctness and scalability issues. Most of the distance-based algorithms for inferring phylogenetic trees follow the closest pair joining scheme. This is one of the approaches used in hierarchical clustering. Moreover, although phylogenetic inference algorithms may seem rather different, the main difference among them resides on how one defines cluster proximity and on which optimization criterion is used. Both cluster proximity and optimization criteria rely often on a model of evolution. In this work, we review, and we provide a unified view of these algorithms. This is an important step not only to better understand such algorithms but also to identify possible computational bottlenecks and improvements, important to deal with large data sets.

Chewie Nomenclature Server (chewie-NS): a deployable nomenclature server for easy sharing of core and whole genome MLST schemas.

Chewie Nomenclature Server (chewie-NS, https://chewbbaca.online/) allows users to share genome-based gene-by-gene typing schemas and to maintain a common nomenclature, simplifying the comparison of results. The combination between local analyses and a public repository of allelic data strikes a balance between potential confidentiality issues and the need to compare results. The possibility of deploying private instances of chewie-NS facilitates the creation of nomenclature servers with a restricted user base to allow compliance with the strictest data policies. Chewie-NS allows users to easily share their own schemas and to explore publicly available schemas, including informative statistics on schemas and loci presented in interactive charts and tables. Users can retrieve all the information necessary to run a schema locally or all the alleles identified at a particular locus. The integration with the chewBBACA suite enables users to directly upload new schemas to chewie-NS, download existing schemas and synchronize local and remote schemas from chewBBACA command line version, allowing an easier integration into high-throughput analysis pipelines. The same REST API linking chewie-NS and the chewBBACA suite supports the interaction of other interfaces or pipelines with the databases available at chewie-NS, facilitating the reusability of the stored data.

Polymerase chain reaction for the in vitro detection of the pESI plasmid associated with the globally circulating Salmonella Infantis outbreak strain.

A globally circulating strain of Salmonella enterica serotype Infantis containing the pESI plasmid has increased in prevalence in poultry meat samples and cases of human infections. In this study, a polymerase chain reaction (PCR) protocol was designed to detect the pESI plasmid and confirm the Infantis serotype of Salmonella isolates. Primers were tested bioinformatically to predict specificity, sensitivity, and precision. A total of 54 isolates of Salmonella serotypes Infantis, Senftenberg, and Alachua were tested, with and without the pESI plasmid carriage. Isolates of 31 additional serotypes were also screened to confirm specificity to Infantis. Specificity, sensitivity, and precision of each primer were >0.95. All isolates tested produced the expected band sizes. This PCR protocol provides a rapid and clear result for the detection of the pESI plasmid and serotype Infantis and will allow for the in vitro detection for epidemiological studies where whole-genome sequencing is not available.

Plasmid ATLAS: plasmid visual analytics and identification in high-throughput sequencing data.

Plasmid ATLAS (pATLAS, http://www.patlas.site) provides an easy-to-use web accessible database with visual analytics tools to explore the relationships of plasmids available in NCBI's RefSeq database. pATLAS has two main goals: (i) to provide an easy way to search for plasmids deposited in NCBI RefSeq and their associated metadata; (ii) to visualize the relationships of plasmids in a graph, allowing the exploration of plasmid evolution. pATLAS allows searching by plasmid name, bacterial host taxa, antibiotic resistance and virulence genes, plasmid families, and by sequence length and similarity. pATLAS is also able to represent in the plasmid network, plasmid sets identified by external pipelines using mapping, mash screen or assembly from high-throughput sequencing data. By representing the identified hits within the network of relationships between plasmids, allowing the possibility of removing redundant results, and by taking advantage of the browsing capabilities of pATLAS, users can more easily interpret the pipelines' results. All these analyses can be saved to a JSON file for sharing and future re-evaluation. Furthermore, by offering a REST-API, the pATLAS database and network display are easily accessible by other interfaces or pipelines.

Two multi-fragment recombination events resulted in the ß-lactam-resistant serotype 11A-ST6521 related to Spain9V-ST156 pneumococcal clone spreading in south-western Europe, 2008 to 2016.

BackgroundThe successful pneumococcal clone Spain9V-ST156 (PMEN3) is usually associated with vaccine serotypes 9V and 14.AimOur objective was to analyse the increase of a serotype 11A variant of PMEN3 as cause of invasive pneumococcal disease (IPD) in Spain and its spread in south-western Europe.MethodsWe conducted a prospective multicentre study of adult IPD in Spain (2008-16). Furthermore, a subset of 61 penicillin-resistant serotype 11A isolates from France, Italy, Portugal and Spain were subjected to whole genome sequencing (WGS) and compared with 238 genomes from the European Nucleotide Archive (ENA).ResultsAlthough the incidence of serotype 11A in IPD was stable, a clonal shift was detected from CC62 (penicillin-susceptible) to CC156 (penicillin-resistant). By WGS, three major 11A-CC156 lineages were identified, linked to ST156 (n = 5 isolates; France, Italy and Portugal), ST166 (n = 4 isolates; France and Portugal) and ST838/6521 (n = 52 isolates; France, Portugal and Spain). Acquisition of the 11A capsule allowed to escape vaccine effect. AP200 (11A-ST62) was the donor for ST156 and ST838/6521 but not for ST166. In-depth analysis of ST838/6521 lineage showed two multi-fragment recombination events including four and seven fragments from an 11A-ST62 and an NT-ST344 representative, respectively.ConclusionThe increase in penicillin-resistant serotype 11A IPD in Spain was linked to the spread of a vaccine escape PMEN3 recombinant clone. Several recombination events were observed in PMEN3 acquiring an 11A capsule. The most successful 11A-PMEN3 lineage spreading in south-western Europe appeared after two multi-fragment recombination events with representatives of two major pneumococcal clones (11A-ST62 and NT-ST344).

PHYLOViZ 2.0: providing scalable data integration and visualization for multiple phylogenetic inference methods.

High Throughput Sequencing provides a cost effective means of generating high resolution data for hundreds or even thousands of strains, and is rapidly superseding methodologies based on a few genomic loci. The wealth of genomic data deposited on public databases such as Sequence Read Archive/European Nucleotide Archive provides a powerful resource for evolutionary analysis and epidemiological surveillance. However, many of the analysis tools currently available do not scale well to these large datasets, nor provide the means to fully integrate ancillary data. Here we present PHYLOViZ 2.0, an extension of PHYLOViZ tool, a platform independent Java tool that allows phylogenetic inference and data visualization for large datasets of sequence based typing methods, including Single Nucleotide Polymorphism (SNP) and whole genome/core genome Multilocus Sequence Typing (wg/cgMLST) analysis. PHYLOViZ 2.0 incorporates new data analysis algorithms and new visualization modules, as well as the capability of saving projects for subsequent work or for dissemination of results. AVAILABILITY AND IMPLEMENTATION: http://www.phyloviz.net/ (licensed under GPLv3). CONTACT: cvaz@inesc-id.ptSupplementary information: Supplementary data are available at Bioinformatics online.

Bacillus invictae sp. nov., isolated from a health product.

A Gram-positive, rod-shaped, endospore-forming Bacillus isolate, Bi.(FFUP1) (T), recovered in Portugal from a health product was subjected to a polyphasic study and compared with the type strains of Bacillus pumilus, Bacillus safensis, Bacillus altitudinis and Bacillus xiamenensis, the phenotypically and genotypically most closely related species. Acid production from cellobiose, D-glucose and D-mannose and absence of acid production from D-arabinose, erythritol, inositol, maltose, mannitol, raffinose, rhamnose, sorbitol, starch and L-tryptophan discriminated this new isolate from the type strains of the most closely related species. Additionally, a significant different protein and carbohydrate signature was evidenced by spectroscopic techniques, matrix-assisted laser desorption/ionization time-of-flight mass spectrometry and Fourier transform IR spectroscopy with attenuated total reflectance. Using a chemometric approach, the score plot generated by principal component analysis clearly delineated the isolate as a separate cluster. The quinone system for strain Bi.(FFUP1) (T) comprised predominantly menaquinone MK-7 and major polar lipids were diphosphatidylglycerol, an unidentified phospholipid and an unidentified glycolipid. Strain Bi.(FFUP1) (T) showed ≥ 99% 16S rRNA gene sequence similarity to B. safensis FO-036b(T), B. pumilus (7061(T) and SAFR-032), B. altitudinis 41KF2b(T) and B. xiamenensis HYC-10(T). Differences in strain Bi.FFUP1 (T) gyrB and rpoB sequences in comparison with the most closely related species and DNA-DNA hybridization experiments with Bi.FFUP1 (T) and B. pumilus ATCC 7061(T), B. safensis FO-036b(T), B. altitudinis 41KF2b(T) and B. xiamenensis HYC-10(T) gave relatedness values of 39.6% (reciprocal 38.0%), 49.9% (reciprocal 42.9%), 61.9% (reciprocal 52.2%) and 61.7% (reciprocal 49.2%), respectively, supported the delineation of strain Bi.(FFUP1) (T) as a representative of a novel species of the genus Bacillus, for which the name Bacillus invictae sp. nov. is proposed, with strain Bi.(FFUP1) (T) ( =DSM 26896(T) =CCUG 64113(T)) as the type strain.

PHYLOViZ: phylogenetic inference and data visualization for sequence based typing methods.

BACKGROUND: With the decrease of DNA sequencing costs, sequence-based typing methods are rapidly becoming the gold standard for epidemiological surveillance. These methods provide reproducible and comparable results needed for a global scale bacterial population analysis, while retaining their usefulness for local epidemiological surveys. Online databases that collect the generated allelic profiles and associated epidemiological data are available but this wealth of data remains underused and are frequently poorly annotated since no user-friendly tool exists to analyze and explore it. RESULTS: PHYLOViZ is platform independent Java software that allows the integrated analysis of sequence-based typing methods, including SNP data generated from whole genome sequence approaches, and associated epidemiological data. goeBURST and its Minimum Spanning Tree expansion are used for visualizing the possible evolutionary relationships between isolates. The results can be displayed as an annotated graph overlaying the query results of any other epidemiological data available. CONCLUSIONS: PHYLOViZ is a user-friendly software that allows the combined analysis of multiple data sources for microbial epidemiological and population studies. It is freely available at http://www.phyloviz.net.

Adjusted Wallace coefficient as a measure of congruence between typing methods.

We propose a new coefficient, the adjusted Wallace coefficient (AW), and corresponding confidence intervals (CI) as quantitative measures of congruence between typing methods. The performance of the derived CI was evaluated using simulated data. Published microbial typing data were used to demonstrate the advantages of AW over the Wallace coefficient.

Analysis of invasiveness of pneumococcal serotypes and clones circulating in Portugal before widespread use of conjugate vaccines reveals heterogeneous behavior of clones expressing the same serotype.

To estimate the invasive disease potential of serotypes and clones circulating in Portugal before extensive use of the seven-valent pneumococcal conjugate vaccine, we analyzed 475 invasive isolates recovered from children and adults and 769 carriage isolates recovered from children between 2001 and 2003. Isolates were serotyped and genotyped by pulsed-field gel electrophoresis, and a selection of isolates were also characterized by multilocus sequence typing. We found that the diversities of serotypes and genotypes of pneumococci responsible for invasive infections and carriage were identical and that most carried clones could also be detected as causes of invasive disease. Their ability to do so, however, varied substantially. Serotypes 1, 3, 4, 5, 7F, 8, 9N, 9L, 12B, 14, 18C, and 20 were found to have an enhanced propensity to cause invasive disease, while serotypes 6A, 6B, 11A, 15B/C, 16F, 19F, 23F, 34, 35F, and 37 were associated with carriage. In addition, significant differences in invasive disease potential between clones sharing the same serotype were found among several serotypes, namely, 3, 6A, 6B, 11A, 14, 19A, 19F, 22F, 23F, 34, and NT. This heterogeneous behavior of the clones was found irrespective of the serotype's overall invasive disease potential. Our results highlight the importance of the genetic background when analyzing the invasive disease potential of certain serotypes and provide an important baseline for its monitoring following conjugate vaccine use. Continuous surveillance should be maintained, and current research should focus on uncovering the genetic determinants that contribute to the heterogeneity of invasive disease potential of clones sharing the same serotype.

Highly penicillin-resistant multidrug-resistant pneumococcus-like strains colonizing children in Oeiras, Portugal: genomic characteristics and implications for surveillance.

While performing surveillance studies in Oeiras, Portugal, designed to describe the impact of pneumococcal conjugate vaccine on colonization, we observed an increase from 0.7% in 2003 to 5% in 2006 in the prevalence of penicillin resistance (MIC of 2 to 6 mg/liter) among presumptively identified pneumococcal isolates. Although 15 of the 22 penicillin-resistant isolates obtained in 2006 were optochin resistant, they were bile soluble and thus considered to be bona fide pneumococci. This study aimed to clarify the nature of these isolates by using a combination of phenotypic and genotypic approaches that included routine strategies for pneumococcal identification, multilocus sequence analysis (MLSA), and comparative genomic hybridization (CGH). By MLSA, all isolates were classified as "streptococci of the mitis group" that, however, were distinct from typical Streptococcus pneumoniae or Streptococcus mitis. A single isolate was identified as Streptococcus pseudopneumoniae. CGH confirmed these findings and further indicated that a considerable part of the proposed pneumococcal core genome is conserved in these isolates, including several pneumococcal virulence genes (e.g., pavA, spxB, cbpE, and cbpD). These results suggest that among pneumococci and closely related streptococci, universal unique phenotypic and genetic properties that could aid species identification are virtually impossible to define. In pneumococcal colonization studies, when atypical strains are found, MLSA and CGH are informative tools that can be used to complement routine tests. In our study, after correct identification of the penicillin-resistant true pneumococci, we found that penicillin resistance levels among pneumococci remained stable from 2003 to 2006.

DEN-IM: dengue virus genotyping from amplicon and shotgun metagenomic sequencing.

Dengue virus (DENV) represents a public health threat and economic burden in affected countries. The availability of genomic data is key to understanding viral evolution and dynamics, supporting improved control strategies. Currently, the use of high-throughput sequencing (HTS) technologies, which can be applied both directly to patient samples (shotgun metagenomics) and to PCR-amplified viral sequences (amplicon sequencing), is potentially the most informative approach to monitor viral dissemination and genetic diversity by providing, in a single methodological step, identification and characterization of the whole viral genome at the nucleotide level. Despite many advantages, these technologies require bioinformatics expertise and appropriate infrastructure for the analysis and interpretation of the resulting data. In addition, the many software solutions available can hamper the reproducibility and comparison of results. Here we present DEN-IM, a one-stop, user-friendly, containerized and reproducible workflow for the analysis of DENV short-read sequencing data from both amplicon and shotgun metagenomics approaches. It is able to infer the DENV coding sequence (CDS), identify the serotype and genotype, and generate a phylogenetic tree. It can easily be run on any UNIX-like system, from local machines to high-performance computing clusters, performing a comprehensive analysis without the requirement for extensive bioinformatics expertise. Using DEN-IM, we successfully analysed two types of DENV datasets. The first comprised 25 shotgun metagenomic sequencing samples from patients with variable serotypes and genotypes, including an in vitro spiked sample containing the four known serotypes. The second consisted of 106 paired-end and 76 single-end amplicon sequences of DENV 3 genotype III and DENV 1 genotype I, respectively, where DEN-IM allowed detection of the intra-genotype diversity. The DEN-IM workflow, parameters and execution configuration files, and documentation are freely available at https://github.com/B-UMMI/DEN-IM).

BacPipe: A Rapid, User-Friendly Whole-Genome Sequencing Pipeline for Clinical Diagnostic Bacteriology.

Despite rapid advances in whole genome sequencing (WGS) technologies, their integration into routine microbiological diagnostics has been hampered by the lack of standardized downstream bioinformatics analysis. We developed a comprehensive and computationally low-resource bioinformatics pipeline (BacPipe) enabling direct analyses of bacterial whole-genome sequences (raw reads or contigs) obtained from second- or third-generation sequencing technologies. A graphical user interface was developed to visualize real-time progression of the analysis. The scalability and speed of BacPipe in handling large datasets was demonstrated using 4,139 Illumina paired-end sequence files of publicly available bacterial genomes (2.9-5.4 Mb) from the European Nucleotide Archive. BacPipe is integrated in EBI-SELECTA, a project-specific portal (H2020-COMPARE), and is available as an independent docker image that can be used across Windows- and Unix-based systems. BacPipe offers a fully automated "one-stop" bacterial WGS analysis pipeline to overcome the major hurdle of WGS data analysis in hospitals and public-health and for infection control monitoring.

Global optimal eBURST analysis of multilocus typing data using a graphic matroid approach.

BACKGROUND: Multilocus Sequence Typing (MLST) is a frequently used typing method for the analysis of the clonal relationships among strains of several clinically relevant microbial species. MLST is based on the sequence of housekeeping genes that result in each strain having a distinct numerical allelic profile, which is abbreviated to a unique identifier: the sequence type (ST). The relatedness between two strains can then be inferred by the differences between allelic profiles. For a more comprehensive analysis of the possible patterns of evolutionary descent, a set of rules were proposed and implemented in the eBURST algorithm. These rules allow the division of a data set into several clusters of related strains, dubbed clonal complexes, by implementing a simple model of clonal expansion and diversification. Within each clonal complex, the rules identify which links between STs correspond to the most probable pattern of descent. However, the eBURST algorithm is not globally optimized, which can result in links, within the clonal complexes, that violate the rules proposed. RESULTS: Here, we present a globally optimized implementation of the eBURST algorithm - goeBURST. The search for a global optimal solution led to the formalization of the problem as a graphic matroid, for which greedy algorithms that provide an optimal solution exist. Several public data sets of MLST data were tested and differences between the two implementations were found and are discussed for five bacterial species: Enterococcus faecium, Streptococcus pneumoniae, Burkholderia pseudomallei, Campylobacter jejuni and Neisseria spp.. A novel feature implemented in goeBURST is the representation of the level of tiebreak rule reached before deciding if a link should be drawn, which can used to visually evaluate the reliability of the represented hypothetical pattern of descent. CONCLUSION: goeBURST is a globally optimized implementation of the eBURST algorithm, that identifies alternative patterns of descent for several bacterial species. Furthermore, the algorithm can be applied to any multilocus typing data based on the number of differences between numeric profiles. A software implementation is available at http://goeBURST.phyloviz.net.

Distinct Phenotypic and Genomic Signatures Underlie Contrasting Pathogenic Potential of Staphylococcus epidermidis Clonal Lineages.

Background: Staphylococcus epidermidis is a common skin commensal that has emerged as a pathogen in hospitals, mainly related to medical devices-associated infections. Noteworthy, infection rates by S. epidermidis have the tendency to rise steeply in next decades together with medical devices use and immunocompromized population growth. Staphylococcus epidermidis population structure includes two major clonal lineages (A/C and B) that present contrasting pathogenic potentials. To address this distinction and explore the basis of increased pathogenicity of A/C lineage, we performed a detailed comparative analysis using phylogenetic and integrated pangenome-wide-association study (panGWAS) approaches and compared the lineages's phenotypes in in vitro conditions mimicking carriage and infection. Results: Each S. epidermidis lineage had distinct phenotypic signatures in skin and infection conditions and differed in genomic content. Combination of phenotypic and genotypic data revealed that both lineages were well adapted to skin environmental cues. However, they appear to occupy different skin niches, perform distinct biological functions in the skin and use different mechanisms to complete the same function: lineage B strains showed evidence of specialization to survival in microaerobic and lipid rich environment, characteristic of hair follicle and sebaceous glands; lineage A/C strains showed evidence for adaption to diverse osmotic and pH conditions, potentially allowing them to occupy a broader and more superficial skin niche. In infection conditions, A/C strains had an advantage, having the potential to bind blood-associated host matrix proteins, form biofilms at blood pH, resist antibiotics and macrophage acidity and to produce proteases. These features were observed to be rare in the lineage B strains. PanGWAS analysis produced a catalog of putative S. epidermidis virulence factors and identified an epidemiological molecular marker for the more pathogenic lineage. Conclusion: The prevalence of A/C lineage in infection is probably related to a higher metabolic and genomic versatility that allows rapid adaptation during transition from a commensal to a pathogenic lifestyle. The putative virulence and phenotypic factors associated to A/C lineage constitute a reliable framework for future studies on S. epidermidis pathogenesis and the finding of an epidemiological marker for the more pathogenic lineage is an asset for the management of S. epidermidis infections.

Author Correction: Critical steps in clinical shotgun metagenomics for the concomitant detection and typing of microbial pathogens.

A correction to this article has been published and is linked from the HTML and PDF versions of this paper. The error has not been fixed in the paper.

Analysis of typing methods for epidemiological surveillance of both methicillin-resistant and methicillin-susceptible Staphylococcus aureus strains.

Sequence-based methods for typing Staphylococcus aureus, such as multilocus sequence typing (MLST) and spa typing, have increased interlaboratory reproducibility, portability, and speed in obtaining results, but pulsed-field gel electrophoresis (PFGE), remains the method of choice in many laboratories due to the extensive experience with this methodology and the large body of data accumulated using the technique. Comparisons between typing methods have been overwhelmingly based on a qualitative assessment of the overall agreement of results and the relative discriminatory indexes. In this study, we quantitatively assess the congruence of the major typing methods for S. aureus, using a diverse collection of 198 S. aureus strains previously characterized by PFGE, spa typing, MLST, and, in the case of methicillin-resistant S. aureus (MRSA), SCCmec typing in order to establish the quantitative congruence between the typing methods. The results of most typing methods agree in that MRSA and methicillin-susceptible S. aureus (MSSA) differ in terms of diversity of genetic backgrounds, with MSSA being more diverse. Our results show that spa typing has a very good predictive power over the clonal relationships defined by eBURST, while PFGE is less accurate for that purpose but nevertheless provides better typeability and discriminatory power. The combination of PFGE and spa typing provided even better results. Based on these observations, we suggest the use of the conjugation of spa typing and PFGE typing for epidemiological surveillance studies, since this combination provides the ability to infer long-term relationships while maintaining the discriminatory power and typeability needed in short-term studies.

High rates of transmission of and colonization by Streptococcus pneumoniae and Haemophilus influenzae within a day care center revealed in a longitudinal study.

Day care centers (DCCs) are unique settings where young children are at increased risk for colonization by pneumococci and Haemophilus influenzae. Although point prevalence studies in DCCs are frequent, only a few longitudinal studies on the dynamics of colonization have been published. We conducted a 1-year longitudinal study with 11 sampling periods on nasopharyngeal carriage of pneumococci and H. influenzae among 47 children who attended a single DCC. All isolates were antibiotyped and genotyped by pulsed-field gel electrophoresis. Pneumococci were also serotyped. Of the 414 samples obtained, 61.4% contained pneumococci, and 87% contained H. influenzae. Only 8.3% of the samples were negative for both species. Twenty-one pneumococcal clones and 47 H. influenzae clones were identified. Introduction of clones occurred during all year. Ninety-eight percent and 96% of all pneumococcal and H. influenzae isolates, respectively, belonged to clones shared by more than one child. Children were sequentially colonized with up to six pneumococcal clones (mean, 3.6) and five serotypes and nine H. influenzae clones (mean, 7.1). Clones with increased capacity for transmission and/or prolonged colonization were identified in both species. These two fitness properties appeared to be independent. In conclusion, among DCC attendees, a high rate of acquisition and turnover of strains was observed, and all children were overwhelmingly colonized by clones shared with others. DCCs are units where permanent introduction of new clones occurs, and attendees, as a whole, provide a pool of hosts where the fittest clones find privileged opportunities to persist and expand.

Large-Scale Simulations of Bacterial Populations Over Complex Networks.

The understanding of bacterial population genetics and evolution is crucial in epidemic outbreak studies and pathogen surveillance. However, all epidemiological studies are limited to their sampling capacities which, by being usually biased or limited due to economic constraints, can hamper the real knowledge of the bacterial population structure of a given species. To this end, mathematical models and large-scale simulations can provide a quantitative analytical framework that can be used to assess how or if limited sampling can infer the true population structure. In this article, we address the large-scale simulation of genetic evolution of bacterial populations, using Wright-Fisher model, in the presence of complex host contact networks. We present an efficient approach for large-scale simulations over complex host contact networks, using MapReduce on top of Apache Spark and GraphX API. We evaluate the relation between cluster computing power and simulations speedup and include insights on how bacterial population diversity can be affected by mutation and recombination rates, and network topology.

Fast phylogenetic inference from typing data.

BACKGROUND: Microbial typing methods are commonly used to study the relatedness of bacterial strains. Sequence-based typing methods are a gold standard for epidemiological surveillance due to the inherent portability of sequence and allelic profile data, fast analysis times and their capacity to create common nomenclatures for strains or clones. This led to development of several novel methods and several databases being made available for many microbial species. With the mainstream use of High Throughput Sequencing, the amount of data being accumulated in these databases is huge, storing thousands of different profiles. On the other hand, computing genetic evolutionary distances among a set of typing profiles or taxa dominates the running time of many phylogenetic inference methods. It is important also to note that most of genetic evolution distance definitions rely, even if indirectly, on computing the pairwise Hamming distance among sequences or profiles. RESULTS: We propose here an average-case linear-time algorithm to compute pairwise Hamming distances among a set of taxa under a given Hamming distance threshold. This article includes both a theoretical analysis and extensive experimental results concerning the proposed algorithm. We further show how this algorithm can be successfully integrated into a well known phylogenetic inference method, and how it can be used to speedup querying local phylogenetic patterns over large typing databases.