Project for CS-251: Design and Analysis of Algorithms
Hereditary diseases collectively affect a significant portion of humanity — approximately 1 in every 17 people will be affected by a rare condition at some point in their lives, the vast majority of which are genetic in origin. It is estimated that 80% of rare diseases have a genetic cause, making hereditary conditions the single largest category of chronically undiagnosed illness.
The diagnostic challenge is compounded by the high cost of genetic screening: commercially available DNA testing kits range from $100 to $2,000 per test, placing them entirely out of reach for populations in low-income countries such as Chad, Niger, and Sudan, where GNI per capita falls below $1,000. The result is a global inequity in which the burden of hereditary disease falls heaviest on those least equipped to diagnose it.
There exists, therefore, a need for an accessible, algorithmic pre-screening tool capable of identifying the likelihood of hereditary disease from raw DNA sequence data — before expensive confirmatory testing is ordered. This project, HelixMatch, addresses this gap by implementing the Smith-Waterman local sequence alignment algorithm, a well-established dynamic programming technique, to align a user-submitted DNA sequence against a curated reference library of known pathogenic mutations sourced from ClinVar and NCBI GenBank. By returning a ranked similarity score against each reference mutation, the system functions as a triage layer — narrowing the diagnostic space so that targeted, disease-specific kits are used only where algorithmic evidence warrants them, rather than broad and costly comprehensive panels. This approach does not replace clinical diagnosis, but meaningfully reduces its cost barrier.
Hereditary diseases are genetic conditions passed from parents to offspring through mutations in germline cells. Common examples include cystic fibrosis, sickle cell disease, and Huntington's disease. A genetic mutation is a permanent change in the nucleotide sequence of DNA, arising from both external causes — such as UV radiation and mutagenic chemicals — and internal causes such as errors during DNA replication. Because many of these diseases are well-characterized at the genomic level, their causative mutation sequences are publicly documented, making sequence comparison a natural algorithmic approach to pre-screening.
Sequence alignment is the process of arranging two or more DNA, RNA, or protein sequences to identify regions of similarity that may reflect shared function or common origin. Alignments are categorized as either global or local. Global alignment aligns two sequences end-to-end in their entirety, and is appropriate when sequences are known to be homologous across their full length. Local alignment, by contrast, identifies the highest-scoring matching subsequence between two strings, making it suitable for cases where only a region of the input is expected to correspond to the reference. Since hereditary mutations are typically short, well-defined sequence variants embedded within a much longer patient genome, local alignment is the appropriate choice for this project.
The canonical algorithm for local sequence alignment is the Smith-Waterman algorithm, introduced by Smith and Waterman in 1981. A naïve brute-force approach to local alignment would enumerate all possible alignments — an exponential operation. Smith-Waterman instead applies dynamic programming, constructing an (M x N) scoring matrix where each cell represents the optimal alignment score for the corresponding subsequences, computed from previously solved subproblems. Negative scores are set to zero rather than carried forward, ensuring that only locally similar regions contribute to the final alignment. This yields a time complexity of O(M x N), where M and N are the lengths of the two sequences — guaranteed optimal for local alignment under the chosen scoring scheme.
While tools such as BLAST (Basic Local Alignment Search Tool) also perform local sequence comparison, they differ fundamentally from HelixMatch in both purpose and methodology. BLAST is a heuristic approximation of the Smith-Waterman algorithm, designed to search massive sequence databases at speed by sacrificing some alignment sensitivity. Studies have consistently demonstrated that the exact Smith-Waterman algorithm yields more accurate alignments than BLAST, which is known to miss alignments that Smith-Waterman finds. For a diagnostic pre-screening application where a missed match could mean a missed disease flag, this accuracy trade-off is unacceptable. Furthermore, BLAST is a broad similarity search tool, while HelixMatch is a targeted diagnostic instrument — aligning input sequences specifically against a curated library of clinically significant pathogenic variants from ClinVar and NCBI GenBank, and returning disease-labelled similarity scores rather than raw database hits. In this manner, HelixMatch is both algorithmically justified and clinically distinct.
HelixMatch is built as a full-stack microservice pipeline to ensure robust and fast processing of genetic data.
- User Input: Through a web-based frontend interface, users can upload or input raw patient DNA sequences (FASTA format). They can then select specific target diseases they wish to screen for from a dropdown library.
- Heuristic Triage (The Gatekeeper): To prevent running computationally heavy algorithms on completely unrelated DNA, a rapid string-matching "Gatekeeper" first checks the patient's sequence for known anchor markers associated with the selected diseases. This showcases possible disease variants instantly.
- Dynamic Programming Engine: If anchors are detected, the DNA is routed to the Smith-Waterman engine, which computes the exact genetic alignment against the targeted mutated references.
- Clinical Scoring (Min-Max Scaling): Because healthy human DNA is 99.9% identical to mutated DNA, raw alignment scores are processed through a mathematical "Zoom Lens" (Min-Max Scaling). This normalizes the top 1% of homology into a 0-100% clinical confidence score, accurately distinguishing between healthy carriers and confirmed variants.
- Report Generation: The backend generates a definitive clinical report. The frontend displays the confidence percentages and allows the user to download a formal, printable PDF of their diagnostic results.
The Smith-Waterman algorithm identifies the best matching subsequence in a localized alignment. It can detect point mutations and allows for gaps within a subsequence, making it ideal for detection of hereditary diseases where variants occur in short windows.
For a Top-Down approach using memoization, the algorithm starts by creating a scoring matrix of size (m+1) x (n+1), where m and n are the lengths of the two sequences. Each cell is computed using the recursive relation:
H[i][j] = max(0, H[i-1][j-1] + match_score, H[i-1][j] + gap, H[i][j-1] + gap)
- Default of 0: Avoids negative scores (local alignment property).
- Diagonal: Bases match or mismatch.
- Gaps: Added for insertions/deletions in respective sequences.
If the score evaluates to a negative number, it is reset to 0, which successfully discards poorly matching regions. Scores from the immediate upper, left, and diagonal cells are evaluated to compute the current cell. The highest score in the entire matrix identifies the optimal local alignment.
- Time Complexity: O(M x N) - Each cell in the matrix is computed exactly once.
- Space Complexity: O(M x N) - Matrix of scores is stored in memory for traceback and score evaluation.
Implementation Notes:
- Intended Dataset: The DNA nucleotide sequence data is sourced from the NCBI Nucleotide database. This provides annotated, publicly available DNA sequences covering a diverse range of mutation-based diseases.
- Reference Standards: HelixMatch utilizes RefSeqGene records (
NG_prefix) as curated reference standards. They are non-redundant and highly accurate. - Test Inputs: Test inputs are sourced from raw genomic contigs (
NT_prefix) representing high-quality human genome sequences, suitable for realistic, non-curated clinical test cases.
Software Tools:
- Data Source: NCBI Nucleotide database (RefSeqGene / ClinVar)
- Backend Server: Node.js, Express.js
- Algorithm / Logic: Custom JavaScript (FASTA Parsing, Smith-Waterman Engine, Clinical Report Engine)
- Frontend: HTML, CSS, JavaScript
- Export: PDFKit (for clinical report generation)