Project Overview: Tracking Flu Strains Using Hyper-Log-Log and k-mer Analysis

Overview presentation and Ideas

Objective

The primary objective of this project is to compare a new flu strain with existing strains by leveraging the HyperLogLog (HLL) algorithm to efficiently estimate the number of unique k-mers in genomic sequences. This method allows for quick and memory-efficient similarity analysis of large-scale genomic data.

Background

HyperLogLog is a probabilistic data structure used for cardinality estimation, which provides an efficient way to count the number of unique elements in a dataset. In the context of genomic analysis, k-mers (subsequences of length k) are commonly used to represent DNA sequences. By comparing the HLL representations of k-mer sets from different strains, we can estimate the Jaccard similarity between these sets, helping us understand the genetic relationship between different flu strains.

Workflow

Data Collection:
- Download and store genomic sequences of existing flu strains in FASTA format.
HyperLogLog Construction for Existing Strains:
- Extract k-mers from the sequences of existing flu strains.
- Construct HLLs from these k-mers.
- Save the HLLs to files for future comparisons.
Processing New Strain:
- Extract k-mers from the genomic sequence of a new flu strain.
- Construct an HLL from these k-mers.
Comparison and Analysis:
- Load the precomputed HLLs of existing strains.
- Compare the HLL of the new strain with each of the existing strains’ HLLs to estimate the Jaccard similarity.
- Output the similarity results, indicating the genetic relationship between the new strain and each existing strain.
Phylogenetic Tree Construction:
- Create a distance matrix from the Jaccard similarities.
- Construct and save a phylogenetic tree (dendrogram) based on the distance matrix.

Code Overview

The provided Python script implements the above workflow, with functions for extracting k-mers, creating and saving HLLs, comparing HLLs to estimate genetic similarities, and constructing a phylogenetic tree.

extract_kmers(sequence, k): Generates k-mers from a sequence.
create_hll_from_sequence(sequence, k=31): Constructs an HLL from k-mers of a sequence.
load_existing_hlls(hll_dir): Loads precomputed HLLs from files.
save_hll(hll, filename): Saves an HLL to a file.
compare_with_existing_strains(new_hll, existing_hlls): Compares a new strain’s HLL with existing HLLs and estimates Jaccard similarities.
create_distance_matrix(existing_hlls): Creates a distance matrix from Jaccard similarities.
plot_dendrogram(distance_matrix, strain_names, output_file): Plots and saves a dendrogram based on the distance matrix.
main(): Orchestrates the workflow of creating, saving, loading, comparing HLLs, and constructing the phylogenetic tree.

Installation Instructions

To install the required packages, create a file named requirements.txt with the following content:

scipy
matplotlib
biopython
datasketch

Then run the following command to install the packages:

pip install -r requirements.txt

Applications

Epidemiological Studies: Quickly identify the genetic similarity between new and existing flu strains, aiding in tracking and understanding the spread of the virus.
Vaccine Development: Identify potential candidates for vaccine development by understanding the genetic differences between circulating strains.
Genomic Research: Efficiently handle large-scale genomic data, providing a scalable solution for comparing genetic sequences.

Conclusion

This project demonstrates an efficient and scalable approach to genomic sequence comparison using HyperLogLog and k-mer analysis. By leveraging probabilistic data structures, we can perform rapid and memory-efficient similarity analysis, providing valuable insights into the genetic relationships between flu strains. The phylogenetic tree constructed from these similarities offers a visual representation of these relationships, aiding in further biological interpretations.

Project Overview: Tracking Flu Strains Using Hyper-Log-Log and k-mer Analysis