Pan-genome Sequence Alignment Algorithm Research

Abstract— With the rapid development of sequence alignment technologies, their role in responding to public health emergencies and epidemic prevention has become increasingly prominent. Compared to traditional linear reference sequences, the pan-genome effectively reduces reference bias and misalignment. However, when facing long reference sequences with abundant repetitive regions, candidate positions may proliferate, thereby compromising alignment efficiency and accuracy. This paper proposes a novel alignment algorithm that integrates elastic degenerate strings with the longest common substring strategy. Single nucleotide polymorphisms (SNPs) are linearly encoded using elastic degenerate symbols, while minimizer indexing is combined with a longest common substring interval–based seed filtering strategy to effectively reduce candidate positions. Experimental validation on simulated datasets demonstrates that the proposed method significantly improves both recall and precision rates, while also achieving high accuracy in fragment localization. Further experiments on real datasets reveal that this method outperforms existing mainstream alignment tools in terms of alignment sensitivity, indicating that the longest common substring–based filtering strategy is well suited for complex genomic regions. Overall, this approach provides an alternative technical pathway for enhancing the accuracy of pan-genome sequence alignment and offers a feasible algorithmic framework for subsequent research on pan-genome alignment and viral mutation analysis.