COVID-19 Evolves in Human Hosts

Yanni Liu, Bing Liu, Jiangtao Cui, Zhi Wang, Yulong Shen, Yueshen Xu, Kaicheng Yao, Yuanfang GuanPreprints.org 2020 · DOI

TL;DR

This paper introduces HA-MLCS, a novel algorithm for analyzing large sets of biological sequences, and uses it to study the evolution of SARS-CoV-2. They found that COVID-19 strains are actively diverging in human hosts and share significant similarities with SARS and MERS, suggesting potential therapeutic avenues.

What Problem Does This Paper Address?

The COVID-19 pandemic presented an urgent need to understand the virus's origins, evolution, and relationship to other coronaviruses. Specifically, researchers wanted to know:

  • How does COVID-19 compare to other known coronaviruses?
  • Is the virus evolving, and if so, how?
  • What are its potential animal hosts?
  • How can this information be used to develop vaccines and treatments?

Traditional methods for analyzing large biological sequence datasets, like those for finding common subsequences (MLCS), struggle with the sheer volume and complexity of genomic data. Existing algorithms are either too slow, too imprecise, or both, making them unsuitable for analyzing tens of thousands of full-length viral genomes.

Methods

The core contribution of this paper is the development of a novel algorithm called HA-MLCS (High-precision Approximate MLCS Algorithm). This algorithm is designed to efficiently and accurately find the Multiple Longest Common Subsequences (MLCS) within large sets of sequences.

Here's a breakdown of its key features:

  • Optimized MLCS-DAG Construction: Instead of building a full, potentially massive, directed acyclic graph (DAG) of all possible subsequences, HA-MLCS constructs an optimized MLCS-DAG by employing a "retention strategy" and a scoring function to prune non-critical points. This significantly reduces computational complexity.
  • Backward Topological Sorting: The algorithm uses a backward topological sort to identify and remove redundant points from the MLCS-DAG, further refining it.
  • Low Space-Time Complexity: The authors claim HA-MLCS achieves a time complexity of O(N log N) and a space complexity of O(dN + |E|), making it suitable for "big sequence data."
  • 100% MLCS Length Precision: While it's an approximate algorithm, HA-MLCS guarantees 100% precision in determining the length of the longest common subsequences.

The paper also utilizes MEGA X, a standard tool for phylogenetic analysis, to construct evolutionary trees from the sequence data.

Datasets

The study analyzed a substantial dataset comprising:

  • ~30,000 complete genome sequences of COVID-19: Sourced from human hosts across 79 countries.
  • 21 genomes from animals and the environment: Including rhinolophines and pangolins.
  • 101 genomes from four known flu-causing coronaviruses: HCov-229E, HCov-OC43, HCov-NL63, and HCov-HKU1.
  • 61 genomes from seven potentially lethal pathogenic viruses: SARS, MERS, Victoria, Lassa, Yamagata, Ebola, and Dengue.

These sequences were obtained from public databases like GenBank (NCBI), GISAID, and the CDC.

Key Insights and Ideas

  • COVID-19 is actively evolving in humans: The most striking finding is the observed steady increase in the divergence of COVID-19 strains isolated from human hosts between December 2019 and May 2020. This suggests the virus is adapting and potentially developing different levels of virulence.
  • Strong similarity to SARS and MERS: COVID-19 shows significant genetic similarity to SARS and MERS, hinting that therapeutic strategies effective against these viruses might also be relevant for COVID-19.
  • Animal hosts are key: The virus also exhibits strong similarities with COVID-19 found in rhinolophines and pangolins, reinforcing the idea of animal reservoirs and potential zoonotic origins.
  • Limited similarity to common flu viruses: Despite some overlapping symptoms, COVID-19 is not closely related to the common flu-causing coronaviruses (HCov-229E, HCov-OC43, etc.), suggesting different treatment approaches are needed.
  • Geographic and temporal divergence: The evolutionary analysis revealed that while China was the first reported outbreak country, its early sequences didn't appear at the earliest branches of the evolutionary tree. This, along with the distribution of sequences from other heavily affected countries, suggests the virus spread widely and evolved along multiple paths.

Key Results

  • HA-MLCS Performance: Experimental results (Tables 3 & 4) show HA-MLCS significantly outperforms existing algorithms like CRO and SA-MLCS in terms of both precision and running time, especially for large datasets. For instance, it achieved 100% MLCS length precision and was orders of magnitude faster than SA-MLCS.
  • Evolutionary Trees: The constructed evolutionary trees (Figures 3-9) visually demonstrate the divergence of COVID-19 strains over time and across different countries.
  • Similarity Matrices: The similarity matrices (Table 5) quantify the genetic relationships, showing high similarity between COVID-19 and SARS/MERS (around 0.82 LCS-based) and lower similarity with flu viruses (around 0.65 LCS-based).

Limitations and Future Work

  • Approximate Nature: While HA-MLCS guarantees 100% precision for MLCS length, the number of MLCS found is based on an approximation due to the pruning of potentially key points. The paper acknowledges this and provides a formula (Eq. 3) to quantify this precision loss.
  • Origin Tracing: While the study provides clues, it notes that definitive evidence for the virus's origin is still lacking.
  • Future Work: The authors suggest their findings have important implications for:
  • Developing more effective COVID-19 diagnostic tools, vaccines, and antibody treatments.
  • Understanding the virus's mutation paths and potential for developing more virulent strains.
  • Improving public health management and quarantine procedures.
  • Exploring drug repurposing based on similarities with SARS and MERS.

Summary updated

Abstract

Today, we are all threatened by an unprecedented pandemic: COVID-19. How different is it from other coronaviruses? Will it be attenuated or become more virulent? Which animals may be its original host? In this study, we analyzed 377 publicly available complete genome sequences for the COVID-19 virus, the previously known flu-causing coronaviruses (HCov-229E, HCov-OC43, HCov-NL63 and HCov-HKU1) and the lethal, pathogenic P3/P4 viruses, SARS, MERS, Victoria, Lassa, Yamagata, Ebola, and Dengue. We found strong similarities between the current circulating COVID-19 and SARS and MERS, as well as COVID-19 in rhinolophines and pangolins. On the contrary, COVID-19 shares little similarity with the flu-causing coronaviruses and the other P3/P4 viruses. Strikingly, we observed divergence of COVID-19 strains isolated from human hosts has steadily increased from December 2019 to March 2020, suggesting COVID-19 is actively evolving in human hosts. From all existing human COVID-19 genome sequences, we calculated the first common model that represents the shared sequences of the human COVID-19 strains, which provides important information for vaccine and antibody development. Geographic and time-course analysis of the evolutionary trees of the human COVID-19 reveals possibly heterogeneous evolutional paths among strains from 21 countries. This finding has important implications to the management of COVID-19 and the development of vaccines.
BibTeX
@misc{liu2020covid,
  author = {Yanni Liu and Bing Liu and Jiangtao Cui and Zhi Wang and Yulong Shen and Yueshen Xu and Kaicheng Yao and Yuanfang Guan},
  title = {{COVID-19 Evolves in Human Hosts}},
  year = {2020},
  doi = {10.20944/preprints202003.0316.v1},
  howpublished = {Preprints.org},
}
Figure