Pith. sign in

REVIEW 2 major objections 37 references

Exhaustive Exact String Matching: The Analysis of the Full Human Genome

T0 review · 2 major / 0 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Ex2SM detects every repeated string up to 50 characters long throughout the entire human genome.

desk verdict The paper's claimed novelty hinges on a mistaken premise about why standard string algorithms cannot handle repeats of length 50. read the letter →

arxiv 1907.11232 v1 pith:MDQWCUJJ submitted 2019-07-24 cs.DS cs.IR

Konstantinos F. Xylogiannopoulos This is my paper · ORCID
classification cs.DScs.IR
keywords stringmatchinghumangenomeanalysisrepeatedsequencesbioinformaticsalgorithmsexhaustivesearchtextminingdatastructures
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper presents a new methodology called Ex2SM that can find all instances where any string appears more than once in a biological sequence. Unlike standard string matching tools that look for one specific pattern, this method scans for every possible repeat without being told what to look for. The authors apply it to the complete human genome and report finding all such repeats with lengths from 1 to 50 characters. A reader would care because traditional approaches cannot handle the enormous number of possible strings at those lengths due to exponential growth in combinations.

What carries the argument

Ex2SM, a pipeline of advanced data structures and algorithms that enumerates all repeated strings in a sequence without requiring a predefined pattern to match.

What would settle it

A direct comparison of the repeats found by Ex2SM against those found by a brute-force check on a small test sequence of known repeats would confirm if all repeats are captured.

Watch

Extended reading notes

Core claim

The Ex2SM methodology is a pipeline of advanced data structures and algorithms explicitly designed for text mining that can detect every possible repeated string in multivariate biological sequences. It is string agnostic and does not require an input string to search for; rather it can detect every string that exists at least twice, regardless of its attributes such as length, frequency, alphabet, overlapping etc. The complexity is demonstrated by detecting all repeated strings with a length of up to 50 characters in the entire human genome.

Load-bearing premise

The combination of data structures and algorithms in the pipeline can handle the exponential number of possible strings up to length 50 without missing repeats or exceeding practical computational limits.

Editorial extensions

If this is right

  • Every repeated string up to length 50 can be identified in large sequences like the human genome.
  • The approach works independently of string attributes including overlaps and alphabet size.
  • It enables exhaustive analysis of repeats that is not feasible with pattern-specific algorithms.
  • Applications extend to other bioinformatics tasks involving pattern detection in sequences.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Cataloging all short repeats could reveal previously unknown patterns in genome organization.
  • The method might scale to even longer strings if computational resources allow.
  • Similar exhaustive searches could be applied to other large datasets such as protein sequences or environmental DNA samples.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 0 minor

Summary. The manuscript presents Ex2SM, a pipeline of advanced data structures and algorithms for exhaustive, string-agnostic detection of all repeated strings (regardless of length, frequency, or overlap) in multivariate biological sequences. It claims to have applied the method to the full human genome, detecting every repeated string of length up to 50—an achievement asserted to be practically impossible with existing algorithms due to the exponential number of permutations.

Significance. If the pipeline were shown to be correct, complete, and efficient, the result would be of interest for repeat detection in genomics. However, the manuscript supplies no complexity analysis, no validation on smaller instances, and no reproducible evidence, so the significance cannot be assessed from the provided material.

major comments (2)
  1. [Abstract] Abstract: the claim that detecting repeats of length 50 'is practically impossible using other algorithms due to the exponential number of possible permutations' is incorrect. Standard methods (suffix arrays, suffix trees, or hashing all n existing k-mers) identify duplicates among the O(n) substrings present in the genome (n≈3e9) in O(n log n) time without ever enumerating 4^50 candidates. This error is load-bearing for the stated motivation and novelty.
  2. [Abstract] Abstract: the central claim of feasibility and completeness for the full human genome rests on an unverified assertion; the manuscript provides no derivation of time/space complexity for the Ex2SM pipeline, no validation experiments on smaller genomes, and no error-rate or completeness measurements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We respond to each major comment below and indicate where revisions will be made.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that detecting repeats of length 50 'is practically impossible using other algorithms due to the exponential number of possible permutations' is incorrect. Standard methods (suffix arrays, suffix trees, or hashing all n existing k-mers) identify duplicates among the O(n) substrings present in the genome (n≈3e9) in O(n log n) time without ever enumerating 4^50 candidates. This error is load-bearing for the stated motivation and novelty.

    Authors: We agree that the statement in the abstract is factually incorrect. Methods such as suffix arrays, suffix trees, and k-mer hashing operate on the O(n) substrings that exist in the input and can identify repeats in O(n log n) time without enumerating the full combinatorial space. The original wording overstated the computational barrier and the uniqueness of the motivation. We will revise the abstract to remove this claim and instead emphasize the string-agnostic, exhaustive nature of the pipeline as the primary contribution. revision: yes

  2. Referee: [Abstract] Abstract: the central claim of feasibility and completeness for the full human genome rests on an unverified assertion; the manuscript provides no derivation of time/space complexity for the Ex2SM pipeline, no validation experiments on smaller genomes, and no error-rate or completeness measurements.

    Authors: The referee is correct that the manuscript contains no formal complexity analysis, no validation experiments on smaller genomes, and no quantitative completeness or error-rate measurements. These omissions weaken the verifiability of the claims. We will add a dedicated section deriving the time and space complexity of the pipeline stages and include validation results on smaller genomes together with basic completeness checks. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: algorithmic pipeline presented without self-referential reductions or fitted predictions

full rationale

The paper introduces Ex2SM as a pipeline of data structures and algorithms for exhaustive repeat detection in sequences. No equations, parameters, or derivations appear in the provided text. Claims rest on the described methodology's ability to enumerate existing repeats (not 4^50 candidates) and experimental results on the human genome. No self-citations, ansatzes, or renamings reduce any result to its inputs by construction. The central claim is an empirical demonstration, not a mathematical derivation that collapses.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the central claim implicitly assumes that standard data structures can be composed to solve an exponentially hard enumeration problem without additional ad-hoc mechanisms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exhaustive Exact String Matching: The Analysis of the Full Human Genome." pith.science (2026). https://pith.science/paper/MDQWCUJJ

@misc{pith2026190711232,
  author       = {Pith},
  title        = {Pith review of: Exhaustive Exact String Matching: The Analysis of the Full Human Genome},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MDQWCUJJ}},
  note         = {Machine review of arXiv:1907.11232}
}
read the original abstract

Exact string matching has been a fundamental problem in computer science for decades because of many practical applications. Some are related to common procedures, such as searching in files and text editors, or, more recently, to more advanced problems such as pattern detection in Artificial Intelligence and Bioinformatics. Tens of algorithms and methodologies have been developed for pattern matching and several programming languages, packages, applications and online systems exist that can perform exact string matching in biological sequences. These techniques, however, are limited to searching for specific and predefined strings in a sequence. In this paper a novel methodology (called Ex2SM) is presented, which is a pipeline of execution of advanced data structures and algorithms, explicitly designed for text mining, that can detect every possible repeated string in multivariate biological sequences. In contrast to known algorithms in literature, the methodology presented here is string agnostic, i.e., it does not require an input string to search for it, rather it can detect every string that exists at least twice, regardless of its attributes such as length, frequency, alphabet, overlapping etc. The complexity of the problem solved and the potential of the proposed methodology is demonstrated with the experimental analysis performed on the entire human genome. More specifically, all repeated strings with a length of up to 50 characters have been detected, an achievement which is practically impossible using other algorithms due to the exponential number of possible permutations of such long strings.

Figures

Figures reproduced from arXiv: 1907.11232 by the authors.

Figure 1
Figure 1. Suffix Array and LERP-RSA for CATTATTAGGA B. ARPaD Algorithm When the LERP-RSA data structure is completed then we use the All Repeated Patterns Detection (ARPaD) algorithm. The algorithm has two versions, the recursive left-to-right and the non-recursive top-to-bottom [22]. Both versions have the same time complexity 𝑂(𝑛𝑙𝑜𝑔𝑛). The recursive works as follows. It starts with the first letter of the alphabet, A, and c… view at source ↗
Figure 3
Figure 3. Multivariate LERP-RSA for CATTATTAGGA and CATTCA D. MLERP-ARPaD Algorithm As was described in Section IV.B, biological sequences do not have the randomness property and, therefore, it is expected that LERP Theorem will not provide the appropriate value for the LERP-RSA construction. In order to bypass this problem, we can use the Moving LERP algorithm, specifically design to solve this problem. The MLERP works as fo… view at source ↗
Figure 4
Figure 4. MLERP algorithm example for initial LERP value 3 E. Metadata Analyses After the completion of the data analysis and pattern detection on multiple strings, several metadata analyses can be performed. These analyses depend on several factors such as comparing areas of different chromosomes from the same [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figures from the paper (2 more)
Figure 5
Figure 5. Figure 5: Exhaustive Exact Pattern Matching Pipeline (Ex2SM) The overall space and time complexity of the methodology presented here is 𝑂(𝑛𝑙𝑜𝑔𝑛). In Table I we can observe that each component of the pipeline has loglinear time complexity except the construction of the LERP-RSA w…
Figure 6
Figure 6. Figure 6: Patterns frequency with a length 50 per chromosome and class TABLE III. OCCURRENCES PER CLASS Class Patterns with 2 Occurrences Percentage of Patterns with 2 Occurrences Patterns with 2 Occurrences at the Same Chromosome Percentage of Patterns Occurring in same Chromos…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Construct the LERP-RSA for each string (1..n) and class (1..m)

    work page

  2. [2]

    Merge LERP-RSA from all strings per class (1..m)

    work page

  3. [3]

    Execute ARPaD on M ultivariate/Multivariable LERP-RSA for each class (1..m)

    work page

  4. [4]

    If patterns with a length equal to LERP have been detected then execute MLERP by setting SPL equal to LERP, increasing LERP and repeating from step (1) for positions belonging to patterns found with length exactly LERP, otherwise continue

    work page

  5. [5]

    Perform metadata analyses Fig. 5. Exhaustive Exact Pattern Matching Pipeline (Ex2SM) The overall space and time complexity of the methodology presented here is 𝑂(𝑛𝑙𝑜𝑔𝑛). In Table I we can observe that each component of the pipeline has loglinear time complexity except the construction of the LERP -RSA which is linear , while the space complexity for the s...

    work page

  6. [6]

    Fast pattern matching in strings

    Knuth D.E., Morris J.H., Pratt V.R. (1977). “Fast pattern matching in strings.” SIAM Journal on Computing, 6(2), pp. 323-350

    work page 1977

  7. [7]

    A fast string searching algorithm

    Boyer, R. S. and Moore, J. S . (1977). “A fast string searching algorithm.” Communications of the ACM, pp. 762-772

    work page 1977

  8. [8]

    The Boyer -Moore-Galil String Searching Strategies Revisited

    Apostolico, A. and Giancarlo, R. (1986) “ The Boyer -Moore-Galil String Searching Strategies Revisited.” (in English), SIAM Journal on Computing, 15(1), pp. 98-105

    work page 1986

Show all 37 references
  1. [9]

    Speeding up two string-matching algorithms

    Crochemore, M., Czumaj, A., Gasieniec, L., Jarominek, S., Lecroq, T., Plandowski, W., Rytter, W., (1994) “Speeding up two string-matching algorithms.” Algorithmica, pp. 247-267

    1994

  2. [10]

    An Enhanced Boye -Moore Algorithm (Doctoral dissertation)

    Ahmad, M. K. (2014) “ An Enhanced Boye -Moore Algorithm (Doctoral dissertation).” Middle East University

    2014

  3. [11]

    Hybrid pattern -matching algorithm based on BM -KMP algorithm

    Xian-Feng, H., Yu-Bao, Y., Xia, L. (2010) “Hybrid pattern -matching algorithm based on BM -KMP algorithm.” 3rd International Conference In Advanced Computer Theory and Engineering (ICACTE), (5), pp. 310

    2010

  4. [12]

    A fast string matching algorithm based on lowlight characters in the pattern

    Cao, Z., Zhenzhen, Y., Lihua, L. (2015) “A fast string matching algorithm based on lowlight characters in the pattern.” 7th International Conference on Advanced Computational Intelligence (ICACI), pp. 179-182

    2015

  5. [13]

    A string matching algorithm fast on the average

    Commentz-Walter, B. (1979). “A string matching algorithm fast on the average.” Springer, pp. 118-132

    1979

  6. [14]

    Simple optimal string matching algorithm

    Allauzen, R. (2000). “ Simple optimal string matching algorithm .” Algorithms, pp. 102-116

    2000

  7. [15]

    Efficient online timed pattern matching by automata -based skipping

    Masaki, W., Hasuo, I., Suenag, K. (2017) “Efficient online timed pattern matching by automata -based skipping.” International Conference on Formal Modeling and Analysis of Timed Systems, Springer, pp. 224-243

    2017

  8. [16]

    Suffix Type String Matching Algorithms Based on Multi -windows and Integer Comparison

    Hongbo, F., Shupeng, S., Jing, Z., Li., D. (2015) “ Suffix Type String Matching Algorithms Based on Multi -windows and Integer Comparison." In International Conference on Information and Communications Security, Springer, pp. 414-420

    2015

  9. [17]

    A simple fast hybrid pattern matching algorithm

    Franek, F. J., Jennings, C.G., Smyth, W.F. (2007) “A simple fast hybrid pattern matching algorithm." Journal of Discrete Algorithms, pp. 682- 695

    2007

  10. [18]

    NR -grep: a fast and flexible pattern -matching tool

    Navarro, G. (2001) “NR -grep: a fast and flexible pattern -matching tool.” Softw., Pract. Exper., 31, 1265-1312

    2001

  11. [19]

    A simple tree pattern -matching algorithm

    Lu, H. T. and Yang, W. (2001) “A simple tree pattern -matching algorithm.” i n Proceedings of the Workshop on Algorithms and Theory of Computation

    2001

  12. [20]

    Exact String Matching Algorithms: Survey, Issues and Future Reseach Directions

    Hakak, S., Kamsin, A., Shivakumara, P., Gilkar, G. A., Khan, W. Z., Imran, M. (2017) “Exact String Matching Algorithms: Survey, Issues and Future Reseach Directions”. Preparation of Pape rs for IEEE Transcations and Journals, 2017

    2017

  13. [21]

    Evaluation and Improvement of Fast Algorithms for Exact Matching on Genome Sequences

    Faro, S. (2016). “Evaluation and Improvement of Fast Algorithms for Exact Matching on Genome Sequences.” AlCoB

    2016

  14. [22]

    String Matching in DNA Databases

    Chen, Y. (2018). “String Matching in DNA Databases”, Open Access Biostatistics and Bioinformatics, 1(4)

    2018

  15. [23]

    What is a Random String?

    Calude, C., (1995) “What is a Random String?” Journal of Universal Science, 1(1), pp. 48–66

    1995

  16. [24]

    Suffix arrays: a new method for on-line string searches

    Manber, U. and Myers, G., (1990) “Suffix arrays: a new method for on-line string searches.” Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 319–327

    1990

  17. [25]

    Analyzing very large time series using suffix arrays

    Xylogiannopoulos, K. F. , Karampelas, P., Alhajj, R. (2014) “Analyzing very large time series using suffix arrays” Appl. Intell., 41(3), pp.941–955

    2014

  18. [26]

    Repeated patterns detection in big data using classification and parallelism on LERP reduced suffix arrays

    Xylogiannopoulos, K. F., Karampelas, P., Alhajj, R. (2016) “Repeated patterns detection in big data using classification and parallelism on LERP reduced suffix arrays” Appl. Intell., 45(3), pp. 567– 597

    2016

  19. [27]

    Data structures, algorithms and applications for big data analytics: single, multiple and all repe ated patterns detection in discrete sequences

    Xylogiannopoulos, K. F. , (2017) “Data structures, algorithms and applications for big data analytics: single, multiple and all repe ated patterns detection in discrete sequences.” PhD thesis

    2017

  20. [28]

    Experiments with a Very Fast Substring Search Algorithm

    Smith, P.D. (1991) “Experiments with a Very Fast Substring Search Algorithm.” Softw., Pract. Exper., 21, 1065-1074

    1991

  21. [29]

    The exact s tring matching algorithms efficiency review

    AbdulRazzaq, A. A., Rashid, N. A. A., Hasan, A. A., Abu-Hashem, M. A, “The exact s tring matching algorithms efficiency review .” Global Journal on Technology, pp. 576-589, 2013

    2013

  22. [30]

    Efficient Randomized Pattern- Matching Algorithms

    Karp, R. M. and Rabin, M. O. (1987) “Efficient Randomized Pattern- Matching Algorithms.” IBM Journal of Research and Development, 31(2), pp. 249-260

    1987

  23. [31]

    Fast exact string matching algorithms

    Lecroq, T. (2007) “Fast exact string matching algorithms.” Information Processing Letters, 102(6), pp. 229-235

    2007

  24. [32]

    A fast algorithm for multi -pattern searching

    Wu, S. and Manber, U. (1994) “ A fast algorithm for multi -pattern searching.” Department of Computer Science, University of Arizona, Tucson, AZ, Report TR-94-17

    1994

  25. [33]

    National Center for Biotechnology Information (NCBI) ftp://ftp.ncbi.nlm.nih.gov/genomes/Homo_sapiens/

  26. [34]

    Tuning the Boyer-Moore-Horspool string searching algorithm

    Raita, T. (1992) “Tuning the Boyer-Moore-Horspool string searching algorithm.” Software: Practice and Experience, pp. 879-884

    1992

  27. [35]

    Identification of Common Molecular Subsequences

    Smith, T. F. and Waterman, M. S. (1981) "Identification of Common Molecular Subsequences" Journal of Molecular Biology. 147 (1): 195– 197

    1981

  28. [36]

    National Center for Biotechnology Information (NCBI) https://blast.ncbi.nlm.nih.gov/Blast.cgi

  29. [37]

    Google pi-api https://pi.delivery/

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.