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