Bioinformatics DNA Sequence Alignment Tool
Build a Perl command-line tool that finds the best matching region between two DNA sequences, a task at the heart of bioinformatics, using the Smith-Waterman local alignment algorithm, which you'll implement yourself with dynamic programming. It reads sequences from FASTA files with BioPerl, fills a score matrix using match, mismatch and gap penalties you can configure, traces back the best alignment, and prints it the way biologists read it, with the matching positions marked between the two sequences, plus the score and percentage identity. You'll learn dynamic programming, the Smith-Waterman algorithm and its traceback, reading biological file formats with BioPerl, and checking results against known examples.
- Estimate
- ~10.5h
- Steps
- 6
- Completed by
- 0
- Proposed by
- codeseed.app
BioPerl
Project roadmap
- 01
Read the sequences
~1.5hInstall BioPerl and use Bio::SeqIO to read one sequence from each of two FASTA files (or the first two from one file), with Getopt::Long options for the files. Check the sequences contain only valid DNA letters (A, C, G, T and N), converting to uppercase, and report the sequence ids and lengths. Warn when sequences are very long, since the matrix grows with the product of the lengths. Done when: the tool prints the ids and lengths of two sequences read from FASTA files.
- 02
Fill the score matrix
~2hImplement the Smith-Waterman recurrence: each cell is the maximum of 0, the diagonal cell plus the match or mismatch score, and the cell above or to the left minus the gap penalty. Store the scores in an array of arrays, and track the highest score and its position. Make the match, mismatch and gap scores options (defaults such as +2, -1 and -2). Done when: the matrix for a small textbook example matches the published values.
- 03
Trace back the alignment
~2hStarting from the highest cell, follow the path back (diagonal, up or left, whichever produced the cell's score) until reaching a cell with 0, building the two aligned sequences with - for gaps. Store which direction each cell came from while filling the matrix to make traceback simple. Done when: the alignment for the textbook example matches the published alignment.
- 04
Print the alignment
~1.5hPrint the alignment in blocks of 60 columns, with the start and end positions of each line in the original sequences, and a middle line with | for matches, . for mismatches and spaces for gaps. Print the score, the alignment length, percentage identity and the number of gaps. Add --matrix to print the score matrix for small inputs, which is useful for learning. Done when: the output is readable and the statistics are correct.
- 05
Add affine gaps and options
~2hAdd affine gap penalties (a higher cost to open a gap than to extend it, as real tools use) with three matrices (Gotoh's method), as an option. Add --top N to report several non-overlapping local alignments. Compare the results with the same sequences aligned by EMBOSS Water or an online tool. Done when: your results match a standard tool on a few real sequence pairs.
- 06
Test it
~1.5hWrite Test::More tests with known examples: identical sequences, sequences with no similarity (score 0), a single mismatch, a single gap, affine gaps, and invalid input files. Measure how the running time grows with sequence length and note it in README.md. Done when: prove -l t/ passes, and README.md describes the performance.
Resources
Ready to build this?
Get a GitHub repo and start building. Your AI reviewer checks each step as you go.
Tech stack