TIPE: A Bounded and Signature-Aware Framework for Path Construction in Genome Graphs
IEEE Access · 2026 · 14 · 108558-108570
DOI: 10.1109/access.2026.3714091 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Access, 2026. Verfasst von Dimitris Kalatzis. Die Arbeit nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Graph-based representations are increasingly used to model genomic variation, enabling richer descriptions than linear reference sequences. However, scalable enumeration and indexing of paths in such graphs remain challenging due to the combinatorial growth of possible traversals. We propose TIPE (Tag-Based Iterative Path Expansion), a general framework for bounded, signature-aware path construction in directed graphs. TIPE decouples path expansion from path retention by combining tag-controlled local expansion with explicit, signature-based bounded retention. At each iteration, only anchor states participate in expansion, while a bounded number of representative paths is retained per signature class. This design enables early and sustained control of path growth without materializing the full exponential set of candidate paths. The computational behavior of the framework is governed primarily by the choice of the retention signature rather than by the expansion mechanism itself, motivating the general TIPE formulation. The proposed framework provides a principled and interpretable approach to scalable path construction, supporting controlled exploration of complex genome graphs while preserving representative structural diversity. In the evaluated high-branching settings, TIPE preserves structurally valid paths under bounded exploration, including paths that may not be captured by haplotype-only traversal. Under output-size-matched comparison, TIPE achieves higher exact recall than deterministic beam-style retention and comparable recall to stochastic random pruning, while providing deterministic and explicitly structured coverage of the signature space.
Zitieren
APA
Kalatzis, D. (2026). TIPE: A Bounded and Signature-Aware Framework for Path Construction in Genome Graphs. IEEE Access, 14, 108558-108570. https://doi.org/10.1109/access.2026.3714091
Vancouver
Kalatzis D. TIPE: A Bounded and Signature-Aware Framework for Path Construction in Genome Graphs. IEEE Access. 2026;14:108558-108570. doi:10.1109/access.2026.3714091
BibTeX
@article{Kalatzis2026,
author = {Kalatzis, Dimitris},
title = {TIPE: A Bounded and Signature-Aware Framework for Path Construction in Genome Graphs},
journal = {IEEE Access},
year = {2026},
volume = {14},
pages = {108558--108570},
doi = {10.1109/access.2026.3714091}
}
EUVIMED