This repository contains the implementation, benchmark dataset (OrthoSet), and analysis for evaluating and improving approximate edit distance algorithms. It was developed as a final project for CSE 566 at Penn State University.
Calculating Levenshtein edit distance is a fundamental operation in bioinformatics, but the quadratic complexity of exact algorithms like Needleman-Wunsch makes them impractical for large-scale genomic comparisons. While heuristics like ApproxAlign [WABI 2020] promise near-linear time performance, they often lack comprehensive empirical validation on diverse biological data. Furthermore, there is a scarcity of publicly available, large-scale benchmark datasets containing orthologous sequences with ground-truth edit distances needed for such testing.
This project addresses these gaps by:
- Creating OrthoSet: A novel, large-scale benchmark dataset to facilitate rigorous evaluation.
- Implementing and Analyzing Heuristics: Empirically testing a baseline interpretation of the ApproxAlign algorithm to understand its practical limitations.
- Developing Improved Methods: Designing advanced heuristic (ApproxAlign++) and machine learning (FeatureBased_XGBoost) solutions to achieve a better balance of accuracy and efficiency.
This project provides three core contributions:
- OrthoSet Dataset: A benchmark set of 26,958 orthologous gene pairs (Human-Mouse/Zebrafish) with ground-truth edit distances and rich annotations.
- New algorithms:
- ApproxAlign++: A redesigned heuristic using modern alignment techniques like spaced seeds, LIS anchor chaining, and exact DP gap-filling.
- FeatureBased_XGBoost: A machine learning regressor for rapid, alignment-free estimation from sequence features.
- Baselines: Implementations of exact DP (edlib) and a rudimentary ApproxAlign interpretation for comparison.
- / (root): Contains implementations of the core algorithms:
- approxalign_plus.py: The improved ApproxAlign++ heuristic.
- ml_feature_regressor.py: The FeatureBased_XGBoost regressor.
- approxalign_impl.py: The rudimentary baseline implementation.
- baseline_dp.py: Wrapper for the exact edlib algorithm.
- /dataset_fetch_src: All scripts used to download, process, and create the OrthoSet benchmark dataset from NCBI data.
- /results: Contains all output data, including the final performance summary (edit_distance_summary.csv), raw predictions, and generated plots comparing the methods.