BURA Collection:

Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast

2026-09-03T02:01:03Z

Title: Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast Authors: Ayad, Lorraine AK; Loukides, Grigorios; Pissis, Solon P; Verbeek, Hilde Abstract: Sparse suffix sorting is the problem of sorting b = o(n) suffixes of a string of length n. Efficient sparse suffix sorting algorithms have existed for more than a decade. Despite the multitude of works and their justified claims for applications in text indexing, the existing algorithms have not been employed by practitioners. Arguably this is because there are no simple, direct, and efficient algorithms for sparse suffix array construction. We provide two new algorithms for constructing the sparse suffix and LCP arrays that are simultaneously simple, direct, small, and fast. In particular, our algorithms are: simple in the sense that they can be implemented using only basic data structures; direct in the sense that the output arrays are not a byproduct of constructing the sparse suffix tree or an LCE data structure; fast in the sense that they run in O(n log b) time, in the worst case, or in O(n) time, when the total number of suffixes with an LCP value greater than is in 2^{⌊log n/b⌋+1} − 1 is in O(b/log b), matching the time of optimal yet much more complicated algorithms [Gawrychowski and Kociumaka, SODA 2017; Birenzwige et al., SODA 2020]; and small in the sense that they can be implemented using only 8b + o(b) machine words. Our algorithms are non-trivial space-efficient adaptations of the Monte Carlo algorithm by I et al. for constructing the sparse suffix tree in O(n log b) time [STACS 2014]. We provide extensive experiments to justify our claims on simplicity and on efficiency. A preliminary version of this paper appeared in the proceedings of LATIN 2024. Description: Data Availability: The datasets used are publicly available at the provided links.; A preprint version of the article is available in arXiv, arXiv:2310.09023v2 [cs.DS] (https://arxiv.org/abs/2310.09023). It has not been certified by peer review. Comments: LATIN 2024 + experiments. Submission history: From: Solon Pissis: [v1] Fri, 13 Oct 2023 11:34:13 UTC (1,365 KB); [v2] Thu, 4 Jul 2024 12:09:30 UTC (3,579 KB).

Resilient Pattern Mining

2026-09-03T02:01:04Z

Title: Resilient Pattern Mining Authors: Bian, Pengxin; Charalampopoulos, Panagiotis; Ayad, Lorraine AK; Mohamed, Manal; Pissis, Solon P; Loukides, Grigorios Abstract: Frequent pattern mining is a flagship problem in data mining. In its most basic form, it asks for the set of substrings of a given string S of length n that occur at least τ times in S, for some integer τ ϵ[1,n]. We introduce a resilient version of this classic problem, which we term the (τ, k)-Resilient Pattern Mining (rpm) problem. Given a string S of length n and two integers τ, k in[1, n, RPM asks for the set of substrings of S that occur at least τ times in S, even when the letters at any k positions of S are substituted by other letters. Unlike frequent substrings, resilient ones account for the fact that changes to string S are often expensive to handle or are unknown. We make the following contributions. First, we present RPM-DP, a simple exact O(n³k n)-time and O(n²)-space algorithm for RPM that is based on an existing dynamic programming algorithm. Second, we propose RPM-ESA, an exact O(n log n) -time and O(n) -space algorithm for RPM, which employs advanced data structures and combinatorial insights. Third, we conduct experiments on real large-scale datasets from different domains demonstrating that: (I) The notion of resilient substrings is useful in analyzing genomic data and fundamentally different from that of frequent substrings, as frequent substrings are often not resilient and thus do not remain frequent for long in versioned datasets; (II) RPM-ESA is several orders of magnitude faster and more space-efficient than RPM-DP; and (III) Clustering based on resilient substrings is effective.

Novel Methylation Markers in a Prostate Cancer Cohort are Associated with Disease Development and Relapse

2026-08-29T02:01:20Z

Title: Novel Methylation Markers in a Prostate Cancer Cohort are Associated with Disease Development and Relapse Authors: Lach, Radoslaw P; Pita, Sara; Leung, Wing-Kit; Babbage, Anne; Merson, Susan; Hawkins, Steve; Luxton, Hayley; Kay, Jonathan; Whitaker, Hayley C; Woodcock, Dan J; Haberland, Valeriia; Kote-Jarai, Zsofia; Milne-Clark, Toby; O’Neill, Katherine; Brendler-Spaeth, Timothy; Cheung, Melissa; Ko, Matthew; CRUK ICGC Prostate Cancer Group; Dev, Harveer; Butler, Adam; Lambert, Adam; Hamdy, Freddie C; Verrill, Clare; Field, Sally; Bova, G Steve; Foster, Christopher; Neal, David E; Wedge, David C; Gnanapragasam, Vincent J; Warren, Anne Y; Eeles, Ros A; Cooper, Colin S; Brewer, Daniel S; Massie, Charlie E; Lynch, Andy G Abstract: Prostate cancer remains one of the most common cancers among men globally. While significant strides have been made in diagnosis and treatment, understanding the complex genetic and epigenetic underpinnings of the disease remains crucial for guiding intervention and developing more personalized and effective therapies. The importance of DNA methylation in prostate cancer has been known for some time, but important facets of the modulation of the epigenome during carcinogenesis remain obscure, partly because the bulk of cancer methylation data have been produced using microarray technologies. Here we utilise the TruSeq methyl capture method (EPICseq) to profile the, previously defined, UK Prostate ICGC cohort of well-annotated primary prostate cancers. To this we add methylation sequencing of benign tissue from the same men. These data allow us to identify differentially methylated regions distinguishing cancerous and non-cancerous prostate tissue, while identifying numerous genes whose methylation profiles can perform that task as well as distinguishing between classes of prostate cancer. We describe a describe a methylation-based control mechanism for prostate-cancer-associated SNPs, and show that this seems a likely mechanism of action for a SNP near the MMP7 gene. We describe three novel molecular signatures that arise from different aspects of the biology of prostate cancer revealed by sequencing. Each is shown to be an independent classifier of cancers into groups with different expected times to relapse. These consist of patterns in driver gene methylation, strand-specific methylation, and signal arising in mitochondrial reads. We show that these signatures, combined with existing molecular tools, provide a powerful predictor of time to recurrence. By substantially enhancing understanding of prostate cancer risk, detection, and prognosis, we pave the way for the development of clinical practices that will benefit patients and improve outcomes. Description: The article is a preprint version. It has not been certified by peer review.

Proactive Defence of Cyber-Physical Networks Against Coordinated Attacks With Optimal Resource Allocation

2026-08-27T02:00:51Z

Title: Proactive Defence of Cyber-Physical Networks Against Coordinated Attacks With Optimal Resource Allocation Authors: Du, Min; Zhang, Xin; Flynn, David; Wang, Zidong Abstract: Cyber-physical power systems (CPPSs) are more vulnerable to coordinated attacks on cyber-physical networks. In this context, this paper first assesses the impact of coordinated attacks and reveals the interdependence of cyber-physical networks in amplifying system vulnerability. To address this issue, a tri-level cyber-physical network defence (CPND) model is proposed to enable proactive defence of cyber-physical networks through optimal protection resource allocation against coordinated attacks. This model considers the cyber and physical network properties as well as their interdependence in CPPSs. Meanwhile, it incorporates the optimal allocation of control centres, providing more practical defence strategies against coordinated attacks. Then, a Column-and-Constraint Generation (C&CG) with optimality cuts algorithm is developed to solve the proposed CPND model, thereby improving computational efficiency. Numerical simulation results verify the superiority of the proposed approach.