Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911444264550400 |
|---|---|
| author | Li, Xingfu Wang, Yongping |
| author_facet | Li, Xingfu Wang, Yongping |
| contents | A pangenome captures the genetic diversity across multiple individuals simultaneously, providing a more comprehensive reference for genome analysis than a single linear genome, which may introduce allele bias. A widely adopted pangenome representation is a node-labeled directed graph, wherein the paths correspond to plausible genomic sequences within a species. Consequently, evaluating sequence-to-pangenome graph similarity constitutes a fundamental task in pangenome construction and analysis. This study explores the Longest Common Subsequence (LCS) problem and three of its variants involving a sequence and a pangenome graph. We present four polynomial-time reductions that transform these LCS-related problems into the longest path problem in a directed acyclic graph (DAG). These reductions demonstrate that all four problems can be solved in polynomial time, establishing their membership in the complexity class P. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_05193 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph Li, Xingfu Wang, Yongping Data Structures and Algorithms Computational Complexity 05C85, 68Q17, 68R10, 92D20, 92-08 A pangenome captures the genetic diversity across multiple individuals simultaneously, providing a more comprehensive reference for genome analysis than a single linear genome, which may introduce allele bias. A widely adopted pangenome representation is a node-labeled directed graph, wherein the paths correspond to plausible genomic sequences within a species. Consequently, evaluating sequence-to-pangenome graph similarity constitutes a fundamental task in pangenome construction and analysis. This study explores the Longest Common Subsequence (LCS) problem and three of its variants involving a sequence and a pangenome graph. We present four polynomial-time reductions that transform these LCS-related problems into the longest path problem in a directed acyclic graph (DAG). These reductions demonstrate that all four problems can be solved in polynomial time, establishing their membership in the complexity class P. |
| title | Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph |
| topic | Data Structures and Algorithms Computational Complexity 05C85, 68Q17, 68R10, 92D20, 92-08 |
| url | https://arxiv.org/abs/2602.05193 |