A Design and Analysis of Algorithms (DAA) project implementing Naive Pattern Matching and Knuth-Morris-Pratt (KMP) algorithms for efficient DNA sequence analysis. The project includes a C++ console application, an interactive web-based visualization dashboard, and execution time benchmarking for algorithm comparison.

This project demonstrates efficient string pattern matching techniques used in DNA sequence analysis. It compares the performance of the Naive Pattern Matching algorithm with the Knuth-Morris-Pratt (KMP) algorithm.

The project consists of:

• C++ console application
• Interactive web dashboard
• DNA sequence validation
• Random DNA sequence generation
• Pattern occurrence detection
• Performance benchmarking
• Execution time comparison

This project was developed as part of the Design and Analysis of Algorithms (DAA) course.

• ✅ DNA sequence validation (A, C, G, T only)
• ✅ Naive Pattern Matching
• ✅ Knuth-Morris-Pratt (KMP) Algorithm
• ✅ Find all pattern occurrences
• ✅ Random DNA sequence generation
• ✅ Performance benchmarking
• ✅ Execution time comparison
• ✅ Interactive console menu
• ✅ Interactive Web Dashboard
• ✅ Algorithm visualization
• ✅ Performance comparison graph
• ✅ Modular C++ implementation

• Implements both Naive and KMP algorithms.
• Compares execution time of both algorithms.
• Demonstrates practical Design and Analysis of Algorithms concepts.
• Interactive visualization using HTML, CSS and JavaScript.
• Suitable for DAA laboratory and interview preparation.

DNA-Pattern-Matching/
│
├── CPP/
│   └── main.cpp
│
├── web/
│   └── index_modern_dna_strict.html
│
├── screenshots/
│   ├── menu.png
│   ├── pattern-matching.png
│   ├── benchmark.png
│   └── web-dashboard.png
│
├── README.md
├── LICENSE
└── .gitignore

The Naive algorithm compares the pattern with every possible position in the DNA sequence.

KMP preprocesses the pattern using the Longest Prefix Suffix (LPS) array to avoid unnecessary comparisons.

• C++
• HTML5
• CSS3
• JavaScript
• Standard Template Library (STL)
• Chrono Library
• MT19937 Random Number Generator

============================================
   DNA SEQUENCE PATTERN MATCHING PROJECT
============================================

1. Match a pattern in a DNA sequence

2. Run performance benchmark (Naive vs KMP)

3. Exit

DNA Text

ACGTACGTACGTACGT

Pattern

CGTA

Matches Found : 3

Starting Indices :

1
5
9

Text Length : 100000

Pattern Length : 20

Naive Algorithm

Matches : 2

Time : 3.18 ms

-------------------------

KMP Algorithm

Matches : 2

Time : 0.74 ms

This project helped in understanding:

• Design and Analysis of Algorithms
• String Matching Algorithms
• Naive Pattern Matching
• Knuth-Morris-Pratt (KMP)
• Longest Prefix Suffix (LPS)
• Time Complexity Analysis
• DNA Sequence Processing
• Performance Benchmarking
• Modern C++ Programming

• Boyer-Moore Algorithm
• Rabin-Karp Algorithm
• LPS Array Visualization
• Character Comparison Counter
• FASTA File Support
• CSV Report Export
• Performance Charts
• Qt Desktop GUI
• DNA Mutation Detection

g++ CPP/main.cpp -o dna

./dna

g++ CPP/main.cpp -o dna.exe
dna.exe

• Bioinformatics
• DNA Sequence Analysis
• Genome Research
• Pattern Matching
• String Searching
• Algorithm Analysis
• Computational Biology
• Computer Science Education

• Design and Analysis of Algorithms
• DAA
• DNA Pattern Matching
• String Matching
• Naive Algorithm
• Knuth-Morris-Pratt
• KMP
• LPS
• Bioinformatics
• C++
• HTML
• JavaScript
• Algorithm Visualization
• Performance Benchmarking

Ziyaurrahman

B.Tech in Artificial Intelligence & Data Science

Arya College of Engineering & IT, Jaipur

GitHub: https://github.com/ziyaur-12

If you found this project helpful, consider giving it a ⭐ on GitHub.