Trajectories of random walks on Markov sources reveal the structure of complex sequences
PLOS One · 11.11.2026 · 21 (11) · e0359402
DOI: 10.1371/journal.pone.0359402 ↗Kurz gefasst
Fachartikel in der Zeitschrift PLOS One, online erschienen am 11.11.2026. Verfasst von Ali Altunkaya und 2 weiteren Autor:innen. Beteiligte Einrichtung: Arizona State University, Tempe, Arizona, United States of America. Hauptthemen laut MEDLINE: Markov Chains. Die Arbeit nennt 40 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NIA NIH HHS, National Institute of Health, European Comission.
Abstract (Originalsprache)
We highlight a hierarchical property that is found in many sequences, the property of subunit structure, in which sequence symbols are joined together in tightly knit groups to create new subunits at higher levels of organization. Many sequences have strong connections both between the subunits and within the subunits. We propose an information-theoretic method that reveals hierarchical subunit structure in sequences. We use the probability flow of random walks on the Markov source encompassing transitions from subunit to subunit as a proxy for information flow in the sequence. We decompose the sequence into subunits by compressing the description of the information flow within the Markov source that generates the sequence. We illustrate the method by partitioning several real-world sequences whose subunit structure is already known and find that the method detects this known structure with high sensitivity and reliability. We show the relative complexity of different types of sequences in terms of bits per transition step. Finally, we show relative information flow between levels of the sequence within a revealed hierarchy.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Arizona State University, Tempe, Arizona, United States of America.
- The Translational Genomics Research Institute, Phoenix, Arizona, United States of America.
ORCID-Profile: Ali Altunkaya, Nicholas J Schork
Förderung
- NIA NIH HHS
- National Institute of Health
- European Comission
Zitieren
APA
Altunkaya, A., Sen, A., & Schork, N. J. (2026). Trajectories of random walks on Markov sources reveal the structure of complex sequences. PLOS One, 21(11), e0359402. https://doi.org/10.1371/journal.pone.0359402
Vancouver
Altunkaya A, Sen A, Schork NJ. Trajectories of random walks on Markov sources reveal the structure of complex sequences. PLOS One. 2026;21(11):e0359402. doi:10.1371/journal.pone.0359402
BibTeX
@article{Altunkaya2026,
author = {Altunkaya, Ali and Sen, Arunabha and Schork, Nicholas J},
title = {Trajectories of random walks on Markov sources reveal the structure of complex sequences},
journal = {PLOS One},
year = {2026},
volume = {21},
number = {11},
pages = {e0359402},
doi = {10.1371/journal.pone.0359402}
}
EUVIMED