💻 computer science

Stringology-Based Motif Discovery from EEG Signals: an ADHD Case Study

This paper proposes a novel stringology-based framework utilizing order-preserving and Cartesian tree matching to identify recurrent temporal patterns in EEG signals, revealing that individuals with ADHD exhibit higher frequencies of shorter, less stable, and hierarchically simpler motifs compared to controls, thereby offering a new quantitative approach for objective biomarker development in neurodevelopmental disorders.

Original authors: Anat Dahan, Samah Ghazawi

Published 2026-03-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anat Dahan, Samah Ghazawi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine your brain's electrical activity (EEG) as a long, chaotic song being played by a thousand tiny instruments. For years, scientists have tried to understand this song by listening to the volume (how loud the notes are) or the pitch (how fast the notes repeat). They've found that in people with ADHD, the song sometimes sounds "noisier" or has a different mix of high and low notes.

But this new paper asks a different question: What is the actual shape of the melody?

Instead of just listening to the volume or speed, the researchers used a method borrowed from computer science called Stringology. Think of this as treating the brain's electrical signals not as sound waves, but as a long string of letters (like a secret code). They wanted to find the "catchy riffs" or motifs—short, repeating patterns that keep showing up in the song.

Here is the simple breakdown of what they did and what they found, using some everyday analogies:

1. The Two New "Listening" Tools

The researchers used two special tools to analyze these patterns, which are smarter than just looking at the raw numbers:

Tool A: The "Order" Detective (OPM)
- The Analogy: Imagine you are looking at a line of people. You don't care how tall they are (the actual voltage); you only care about their relative height. Is the person in the middle taller than the one on the left? Is the one on the right the shortest?
- What it does: It ignores the "loudness" of the signal and only looks at the shape of the trend. Did the signal go Up-Down-Up? Or Up-Up-Down? This tool is strict; if the order changes even a little, it counts as a different pattern.
Tool B: The "Family Tree" Architect (CTM)
- The Analogy: Imagine taking that same line of people and building a family tree based on who is the "shortest" (the minimum value). The shortest person becomes the "root" of the tree, and the people to their left and right branch out.
- What it does: This tool looks at the hierarchical structure. It's a bit more flexible. It says, "Even if the heights are slightly different, if the family tree structure looks the same, it's the same pattern." It captures the "skeleton" of the wave.

2. The Experiment: ADHD vs. The Control Group

They took brain recordings from 121 children (some with ADHD, some without) while they did a simple counting game. They ran these recordings through the two tools to see what "riffs" kept repeating.

3. The Big Discoveries

Here is what they found, translated into plain English:

A. The ADHD Brain is More "Repetitive" (But in a Bad Way)

The Finding: The ADHD group had more of these repeating patterns than the control group.
The Analogy: Imagine a DJ playing a set. The control group's DJ plays a varied set with many different transitions. The ADHD group's DJ gets stuck in a loop, playing the same short, catchy riff over and over again.
What it means: The brain isn't just "noisy"; it's getting stuck in a rut. It's repeating the same tiny micro-patterns too often, suggesting a lack of flexibility.

B. The Patterns are Shorter and "Jumpy"

The Finding: The repeating patterns in the ADHD group were shorter and had sharper jumps between points.
The Analogy: Think of a car ride.
- Control Group: The car drives smoothly, taking long, winding turns.
- ADHD Group: The car is constantly slamming on the brakes and hitting the gas. It's making short, jerky movements. The "jumps" in the signal were bigger and more frequent.
What it means: The brain's state is unstable. It can't hold a steady rhythm for very long before it snaps into a new, abrupt pattern.

C. The "Tree" is Flatter

The Finding: When they looked at the "Family Tree" structure (CTM), the ADHD group's trees were shallower and had fewer branches.
The Analogy:
- Control Group: Imagine a complex, multi-level office building with many floors and rooms. It has deep, nested structures.
- ADHD Group: Imagine a flat, one-story warehouse. It's wide, but it lacks depth and complexity.
What it means: The brain's activity in ADHD is less organized. It lacks the deep, layered complexity that allows for sophisticated thinking and planning. It's "simpler" in a way that suggests the brain isn't integrating information as well.

4. Why This Matters

Previously, scientists thought ADHD was just about "too much noise" or "wrong frequencies." This paper suggests something deeper: The structure of time itself is different.

Old View: "The brain is loud and chaotic."
New View: "The brain is stuck in short, repetitive loops, it changes its mind too quickly (jumpy), and it lacks deep, complex organization."

The Takeaway

This study is like discovering a new way to read a book. Instead of just counting how many words are on the page (volume) or how fast you read (speed), they looked at the sentence structure.

They found that the "sentences" in the ADHD brain are shorter, more repetitive, and grammatically simpler than in a typical brain. This gives doctors and researchers a new, more precise way to understand what's happening inside the brain, potentially leading to better ways to diagnose and treat ADHD in the future. It turns abstract "brain noise" into a concrete, readable pattern.

1. Problem Statement

Traditional electroencephalography (EEG) analysis for Attention-Deficit/Hyperactivity Disorder (ADHD) relies heavily on spectral power (e.g., theta/beta ratios), event-related potentials (ERPs), and global complexity measures (e.g., entropy, fractal dimension). While these methods have identified general abnormalities, they often summarize neural activity over long time windows or reduce complex signals to averaged statistics. Consequently, they fail to capture fine-grained, recurrent temporal micro-patterns (motifs) that may reveal the specific structural organization and stability of neural dynamics.

The authors argue that ADHD is characterized by atypical temporal organization and disrupted coordination that is not fully explained by amplitude or frequency imbalances alone. There is a need for a computational framework that can identify recurring temporal structures in raw EEG signals that are invariant to amplitude scaling and robust to inter-subject variability.

2. Methodology

The study proposes a novel framework adapting Stringology (algorithmic techniques for string processing) to analyze continuous EEG time series. The core approach involves transforming numerical EEG signals into strings based on relative ordering and structural shape, then applying pattern matching algorithms to discover "motifs."

A. Data Source

Dataset: Publicly available EEG recordings from 121 children (aged 7–12): 61 diagnosed with ADHD (DSM-IV criteria, medicated) and 60 typically developing controls.
Task: Visual attention task involving counting cartoon characters.
Acquisition: 19-channel EEG (10-20 system), sampled at 128 Hz.
Preprocessing: High/low-pass filtering, Independent Component Analysis (ICA) for artifact removal, and 1-in-4 downsampling (resulting in an effective 32 Hz rate) to reduce computational complexity while preserving essential frequency information.

B. Stringology Tools

The study treats each preprocessed EEG channel time series as a "string" and applies two specific matching paradigms:

Order Preserving Matching (OPM):
- Definition: Compares substrings based on the relative ordinal ranking of elements (e.g., $x_i < x_j$ ) rather than absolute values.
- Goal: Identifies motifs with strict ordinal consistency (e.g., a specific rising/falling trend) regardless of amplitude scaling.
- Constraint: Highly sensitive; any deviation in relative order breaks the match.
Cartesian Tree Matching (CTM):
- Definition: Represents a numerical string as a Cartesian Tree (a binary tree where the root is the minimum value, and subtrees are recursively constructed from left and right sub-arrays).
- Goal: Matches motifs based on hierarchical structural shape (the arrangement of local minima and maxima) rather than exact ordinal sequences.
- Constraint: More flexible than OPM; allows minor local ordering variations as long as the global hierarchical structure (nesting of peaks/valleys) remains identical.

C. Analysis Pipeline

Motif Discovery: Identified highly recurrent substrings (motifs) with a support threshold $\ge$ 0.9 (appearing in at least 90% of participants within a group).
Group Specificity: Retained only motifs unique to either the ADHD or Control group.
Feature Extraction: Extracted four categories of features from the discovered motifs:
- Initial: Length, frequency, support, mean amplitude.
- Gradient Dynamics: Max jump, mean jump, standard deviation of jumps, normalized jumps (measuring transition steepness and volatility).
- OPM Rank Features: Rank differences, rank turning points (reversals in direction), and rank correlation.
- CTM Tree Structural Features: Tree max depth, number of leaves, number of branches, and tree balance (symmetry).
Statistical Testing: Used Mann-Whitney U tests with False Discovery Rate (FDR) correction ( $q < 0.05$ ) to compare groups.

3. Key Contributions

Novel Framework: First application of stringology concepts (OPM and CTM) to EEG motif discovery for ADHD, moving beyond spectral and global complexity metrics.
Amplitude Invariance: The methodology isolates temporal structure and shape, making it robust against amplitude differences and inter-subject variability common in EEG.
Multi-Scale Characterization: Simultaneously analyzes fine-scale ordinal trends (OPM) and coarse-scale hierarchical organization (CTM).
Proof-of-Concept: Demonstrates that ADHD neural dysregulation can be quantified through the structure, stability, and recurrence of temporal patterns rather than just signal power.

4. Key Results

A. Motif Frequency and Length

Recurrence: The ADHD group exhibited significantly higher frequencies of group-unique motifs compared to controls, indicating increased neural stereotypy (repetitiveness).
Length:
- OPM Motifs: ADHD motifs were shorter (length 6–7) than controls, suggesting reduced temporal persistence of ordinal patterns.
- CTM Motifs: No significant difference in length (length 9–10), implying that the duration of structurally defined patterns is preserved even if internal organization changes.
- Time Scale: Motif durations ranged from ~0.19s to 0.31s, corresponding to theta-band activity (3–5 Hz), associated with arousal state transitions.

B. OPM Findings (Ordinal Stability)

Gradient Instability: ADHD participants showed significantly higher jump magnitudes (max and mean) and greater variability in jumps across most channels. This indicates more abrupt and volatile transitions between signal states.
Rank Turning Points: The number of rank turning points (reversals in direction) was significantly higher in the ADHD group across all channels. This suggests frequent, unstable reversals in the relative ordering of neural activity.
Spatial Distribution: Effects were most pronounced in frontal and temporal regions (associated with executive control and attention), with weaker effects in central and occipital regions.

C. CTM Findings (Hierarchical Complexity)

Reduced Complexity: ADHD motifs exhibited shallower tree depths, fewer branches, and fewer leaves compared to controls.
Interpretation: This indicates a simplification of hierarchical organization. The EEG waveforms in ADHD have fewer nested extrema and less multilevel structural complexity.
Spatial Distribution: Significant differences were observed primarily in parietal and temporal regions, with selective effects in frontal areas.

5. Significance and Conclusion

The study concludes that ADHD-related EEG alterations are not merely a matter of increased "noise" or reduced complexity in a global sense, but rather a specific dysregulation of temporal architecture:

Increased Repetitiveness: Neural activity relies on a smaller set of recurring patterns (high motif frequency).
Temporal Instability: These patterns are short-lived and characterized by abrupt transitions and frequent directional reversals (high gradient jumps and rank turning points).
Structural Simplification: The hierarchical organization of these patterns is flattened, lacking the deep nesting and complexity seen in typical development.

Implications:

Biomarker Potential: Motif-based features (recurrence, gradient instability, tree depth) offer objective, interpretable biomarkers for ADHD that complement existing spectral and ERP measures.
Clinical Utility: The framework provides a tool for monitoring neurodevelopmental disorders by quantifying the "shape" of neural dysregulation.
Future Directions: The authors suggest extending this analysis to cross-channel interactions (connectivity), linking motifs to specific frequency bands, and validating findings across larger, diverse cohorts and different cognitive tasks.

In summary, this paper establishes that stringology-based motif discovery provides a powerful, complementary lens for understanding ADHD, revealing that the disorder manifests as a loss of hierarchical complexity and temporal stability in recurrent neural patterns, distinct from traditional amplitude-based abnormalities.