matOptimize: a parallel tree optimization method enables online phylogenetics for SARS-CoV-2

  1. Cheng Ye
  2. Bryan Thornlow
  3. Angie Hinrichs
  4. Alexander Kramer
  5. Cade Mirchandani
  6. Devika Torvi
  7. Robert Lanfear
  8. Russell Corbett-Detig
  9. Yatish Turakhia

Reviewed by

Read the full article

Listed in

Log in to save this article

Abstract

Motivation

Phylogenetic tree optimization is necessary for precise analysis of evolutionary and transmission dynamics, but existing tools are inadequate for handling the scale and pace of data produced during the coronavirus disease 2019 (COVID-19) pandemic. One transformative approach, online phylogenetics, aims to incrementally add samples to an ever-growing phylogeny, but there are no previously existing approaches that can efficiently optimize this vast phylogeny under the time constraints of the pandemic.

Results

Here, we present matOptimize, a fast and memory-efficient phylogenetic tree optimization tool based on parsimony that can be parallelized across multiple CPU threads and nodes, and provides orders of magnitude improvement in runtime and peak memory usage compared to existing state-of-the-art methods. We have developed this method particularly to address the pressing need during the COVID-19 pandemic for daily maintenance and optimization of a comprehensive SARS-CoV-2 phylogeny. matOptimize is currently helping refine on a daily basis possibly the largest-ever phylogenetic tree, containing millions of SARS-CoV-2 sequences.

Availability and implementation

The matOptimize code is freely available as part of the UShER package (https://github.com/yatisht/usher) and can also be installed via bioconda (https://bioconda.github.io/recipes/usher/README.html). All scripts we used to perform the experiments in this manuscript are available at https://github.com/yceh/matOptimize-experiments.

Supplementary information

Supplementary data are available at Bioinformatics online.

Article activity feed

  1. Version published to 10.1093/bioinformatics/btac401
  2. ScreenIT

    SciScore for 10.1101/2022.01.12.475688: (What is this?)

    Please note, not all rigor criteria are appropriate for all manuscripts.

    Table 1: Rigor

    NIH rigor criteria are not applicable to paper type.

    Table 2: Resources

    Software and Algorithms
    SentencesResources
    We used the GenBank MN908947.3 (RefSeq NC_045512.2) sequence as the reference for rooting the tree and used the sampling date metadata to derive from our comprehensive tree three subtrees containing the earliest 100K, 1M and 3M samples, referred to as 100K-sample tree, 1M-sample tree, and 3M-sample tree, respectively.
    RefSeq
    suggested: (RefSeq, RRID:SCR_003496)
    matOptimize also parallelizes Fitch-Sankoff computations for different loci and parsing of chunks of VCF using Intel’s TBB library (https://github.com/oneapi-src/oneTBB).
    matOptimize
    suggested: None
    Software Availability: The matOptimize code is available as part of the UShER package (https://github.com/yatisht/usher), which can also be installed via bioconda (https://bioconda.github.io/recipes/usher/README.html).
    UShER
    suggested: None

    Results from OddPub: Thank you for sharing your code.

    Results from LimitationRecognizer: An explicit section about the limitations of the techniques employed in this study was not found. We encourage authors to address study limitations.

    Results from TrialIdentifier: No clinical trial numbers were referenced.

    Results from Barzooka: We did not find any issues relating to the usage of bar graphs.

    Results from JetFighter: We did not find any issues relating to colormaps.

    Results from rtransparent:
    • Thank you for including a conflict of interest statement. Authors are encouraged to include this statement when submitting to a journal.
    • Thank you for including a funding statement. Authors are encouraged to include this statement when submitting to a journal.
    • No protocol registration statement was detected.

    Results from scite Reference Check: We found no unreliable references.

    About SciScore

    SciScore is an automated tool that is designed to assist expert reviewers by finding and presenting formulaic information scattered throughout a paper in a standard, easy to digest format. SciScore checks for the presence and correctness of RRIDs (research resource identifiers), and for rigor criteria such as sex and investigator blinding. For details on the theoretical underpinning of rigor criteria and the tools shown here, including references cited, please follow this link.

  3. Version published to 10.1101/2022.01.12.475688v1 on bioRxiv