2025/07/18 by Michael Itzhaki, Itzhaki, Michael
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.2507.13671
openalex publication_date 2025/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the structure and reconstruction complexity of Manacher arrays. First, we establish a combinatorial lower bound, proving that the number of rooted tandem repeat trees with n+1 genes exceeds the number of distinct Manacher arrays of length n. Second, we introduce a graph-theoretic framework that associates a graph to each Manacher array, where every proper vertex coloring yields a string consistent with the array. Finally, we analyze a reconstruction algorithm by I et al. (SPIRE 2010), showing that it simultaneously achieves a globally minimal alphabet size, uses at most log2(n-1) + 2 distinct symbols, and can be adapted to produce reconstructions over arbitrary alphabets when possible. Our results also resolve an open problem posed by the original authors. Together, these findings advance the combinatorial understanding of Manacher arrays and open new directions for string reconstruction under structural constraints.