We are amidst an ongoing flood of sequence data arising from the application of high-throughput technologies, and a concomitant fundamental revision in our understanding of how genomes evolve individually and within the biosphere. Workflows for phylogenomic inference must accommodate data that are not only much larger than before, but often more error prone and perhaps misassembled, or not assembled in the first place. Moreover, genomes of microbes, viruses and plasmids evolve not only by tree-like descent with modification but also by incorporating stretches of exogenous DNA. Thus, next-generation phylogenomics must address computational scalability while rethinking the nature of orthogroups, the alignment of multiple sequences and the inference and comparison of trees. New phylogenomic workflows have begun to take shape based on so-called alignment-free (AF) approaches. Here, we review the conceptual foundations of AF phylogenetics for the hierarchical (vertical) and reticulate (lateral) components of genome evolution, focusing on methods based on k-mers. We reflect on what seems to be successful, and on where further development is needed.

A recent editorial in Bioinformatics highlights the commonly misunderstood parameter of max_target_seqs in the BLAST alignment tool. The article raises the awareness of common misconceptions associated with a key parameter of BLAST. However, other key parameters, including the most commonly used evalue, have also been under scrutiny recently by the research community. A detailed documentation of these parameters remains lacking. Here we highlight and discuss the frequently misinterpreted feature of E-value specification in BLAST, and how this and other features may not be intuitive to users. These issues underlie the importance for all users to be critical and mindful of the implication of these parameters when interpreting the final search results. The NCBI BLAST alignment tool (Altschul et al., 1990) is one of the most commonly used bioinformatic tools to identify shared sequence similarity based on local alignment between a query sequence and a target sequence found in a database. Recently, Shah et al. (2018) highlighted a commonly misunderstood key parameter of this tool. Specifically, they highlighted the common misconceptions of the parameter –max_target_seqs, and the implications of its specification on the final results; issues related to this parameter, previously reported as ‘bugs’ in online posts (see https://gist.github.com/sujaikumar/504b3b7024eaf3a04ef5 and https://blastedbio.blogspot.com/2015/12/blast-max-target-sequences-bug.html), have not been widely appreciated in the research community. Another (and perhaps the most) frequently used option in BLAST is the filtering of results by the expect (E) value via parameter specification of –evalue. In BLAST, for each alignment between the query and a subject (target) sequence from a database, a bit-score (S) is calculated; an alignment and its S are determined by the specified parameters (e.g. word size, drop-off score for alignment extension, scoring/substitution matrix and gap costs) in the search (Altschul et al., 1990,, 1997; Camacho et al., 2009). The E-value for an alignment with a calculated bit-score X represents the number of alignments with S ≥ X that one would expect by chance in the search. A lower E-value indicates a smaller likelihood of observing the alignment (of score S ≥ X) simply by chance in the database, thus a higher ‘significance’ of the alignment (i.e. and of the match between the two sequences). The resulting E-value is dependent on the length of the query sequence, and the size of the database. According to the BLAST documentation (https://www.ncbi.nlm.nih.gov/books/NBK279690) and the frequently asked questions online (https://blast.ncbi.nlm.nih.gov/Blast.cgi? CMD=Web&PAGE_TYPE =BlastDocs&DOC_TYPE=FAQ), the E-value is meant to provide a ‘convenient way to create a significance threshold for reporting results’. Indeed, this option has been broadly used in numerous studies for almost three decades now to confine sequence-similarity search to a ‘significant’ threshold, and to identify significant similarity shared between two sequences. Many users assume that BLAST alignment hits with E-values less than or equal to the predefined threshold (e.g. 10−5 via the specification of –evalue 1e-5) are identified after the search is completed, in a final step to rank all alignments by E-value, from the smallest (on the top of the list of results) to the largest E-value (at the bottom of the list). However, the E-value filtering step does not occur at the final stage of BLAST; it occurs earlier during the scanning phase (Altschul et al., 1997; Camacho et al., 2009). During this phase, a gapped alignment is generated using less-sensitive heuristic parameters (Camacho et al., 2009); alignments with an E-value that satisfies the defined cut-off are included in the subsequent phase of the BLAST algorithm (and eventually reported). During the final (trace-back) phase, these gapped alignments are further adjusted using more-sensitive heuristic parameters (Camacho et al., 2009), and the E-value for each of these refined alignments is then recalculated. Therefore, non-intuitively perhaps, alignments that would have a final E-value lower than the specified threshold might not be reported among the final results, because they had failed (i.e. E-value larger than this same E-value threshold) at the earlier gapped-alignment stage. The issues related to parameter specifications (that affect how target sequences are reported in the final results) have been reported in a number of online forums. In addition to –evalue and –max_target_seqs, these parameters include –num_descriptions (the number of descriptions), and –num_alignments (the number of alignments) (see https://bioinformatics.stackexchange.com/questions/3409/blast-hits101disappearing-after-changing-evalue and https://bioinformatics.stackexchange.com/questions/2846/why-doesa-very-strong-blast-hit-get-lost-when-i-change-num-alignments-num-desc). These parameters when specified are not filters applied to the final results as one commonly assumes, but they influence the final results indirectly. A good understanding of how these parameters are implemented is important, especially in cases where the query sequences are highly divergent from other known sequences in the database (Rost, 1999). We concur with the call by Shah et al. (2018) to encourage all users to be critical and mindful of the implication of these parameter specifications on the final search results. Running BLAST searches following the ‘current standards’ (e.g. following the approach described in numerous research publications) without an adequate understanding of how each parameter works is not ideal. When in doubts, one may run the program at default settings and apply the filtering criteria directly on the results after the search is completed. We also recommend that the development team of BLAST to provide a more-explicit documentation on the implementation of these options in the algorithm, and how they would affect the final results. We thank Mark Ragan for his critical reading of this manuscript. RAGP is supported by an International Postgraduate Research Scholarship and a University of Queensland Centenary Scholarship. TGS is supported by an Australian Government Research Training Program (RTP) Scholarship. This work is supported by an Australian Research Council grant (DP150101875) awarded to Mark Ragan and C.X.C. Conflict of Interest: none declared.

BACKGROUND: Clustering sequences into groups of putative homologs (families) is a critical first step in many areas of comparative biology and bioinformatics. The performance of clustering approaches in delineating biologically meaningful families depends strongly on characteristics of the data, including content bias and degree of divergence. New, highly scalable methods have recently been introduced to cluster the very large datasets being generated by next-generation sequencing technologies. However, there has been little systematic investigation of how characteristics of the data impact the performance of these approaches. RESULTS: Using clusters from a manually curated dataset as reference, we examined the performance of a widely used graph-based Markov clustering algorithm (MCL) and a greedy heuristic approach (UCLUST) in delineating protein families coded by three sets of bacterial genomes of different G+C content. Both MCL and UCLUST generated clusters that are comparable to the reference sets at specific parameter settings, although UCLUST tends to under-cluster compositionally biased sequences (G+C content 33% and 66%). Using simulated data, we sought to assess the individual effects of sequence divergence, rate heterogeneity, and underlying G+C content. Performance decreased with increasing sequence divergence, decreasing among-site rate variation, and increasing G+C bias. Two MCL-based methods recovered the simulated families more accurately than did UCLUST. MCL using local alignment distances is more robust across the investigated range of sequence features than are greedy heuristics using distances based on global alignment. CONCLUSIONS: Our results demonstrate that sequence divergence, rate heterogeneity and content bias can individually and in combination affect the accuracy with which MCL and UCLUST can recover homologous protein families. For application to data that are more divergent, and exhibit higher among-site rate variation and/or content bias, MCL may often be the better choice, especially if computational resources are not limiting.

BACKGROUND: Genetic recombination can produce heterogeneous phylogenetic histories within a set of homologous genes. These recombination events can be obscured by subsequent residue substitutions, which consequently complicate their detection. While there are many algorithms for the identification of recombination events, little is known about the effects of subsequent substitutions on the accuracy of available recombination-detection approaches. RESULTS: We assessed the effect of subsequent substitutions on the detection of simulated recombination events within sets of four nucleotide sequences under a homogeneous evolutionary model. The amount of subsequent substitutions per site, prior evolutionary history of the sequences, and reciprocality or non-reciprocality of the recombination event all affected the accuracy of the recombination-detecting programs examined. Bayesian phylogenetic-based approaches showed high accuracy in detecting evidence of recombination event and in identifying recombination breakpoints. These approaches were less sensitive to parameter settings than other methods we tested, making them easier to apply to various data sets in a consistent manner. CONCLUSION: Post-recombination substitutions tend to diminish the predictive accuracy of recombination-detecting programs. The best method for detecting recombined regions is not necessarily the most accurate in identifying recombination breakpoints. For difficult detection problems involving highly divergent sequences or large data sets, different types of approach can be run in succession to increase efficiency, and can potentially yield better predictive accuracy than any single method used in isolation.

MOTIVATION: Multiple sequence alignment at the level of whole proteomes requires a high degree of automation, precluding the use of traditional validation methods such as manual curation. Since evolutionary models are too general to describe the history of each residue in a protein family, there is no single algorithm/model combination that can yield a biologically or evolutionarily optimal alignment. We propose a 'shotgun' strategy where many different algorithms are used to align the same family, and the best of these alignments is then chosen with a reliable objective function. We present WOOF, a novel 'word-oriented' objective function that relies on the identification and scoring of conserved amino acid patterns (words) between pairs of sequences. RESULTS: Tests on a subset of reference protein alignments from BAliBASE showed that WOOF tended to rank the (manually curated) reference alignment highest among 1060 alternative (automatically generated) alignments for a majority of protein families. Among the automated alignments, there was a strong positive relationship between the WOOF score and similarity to the reference alignment. The speed of WOOF and its independence from explicit considerations of three-dimensional structure make it an excellent tool for analyzing large numbers of protein families. AVAILABILITY: On request from the authors.