Distance-Based Lempel–Ziv Complexity for the Analysis of Electroencephalograms in Patients with Alzheimer’s Disease

Abstract

The analysis of electroencephalograms (EEGs) of patients with Alzheimer’s disease (AD) could contribute to the diagnosis of this dementia. In this study, a new non-linear signal processing metric, distance-based Lempel–Ziv complexity (dLZC), is introduced to characterise changes between pairs of electrodes in EEGs in AD. When complexity in each signal arises from different sub-sequences, dLZC would be greater than when similar sub-sequences are present in each signal. EEGs from 11 AD patients and 11 age-matched control subjects were analysed. The dLZC values for AD patients were lower than for control subjects for most electrode pairs, with statistically significant differences (p < 0.01, Student’s t-test) in 17 electrode pairs in the distant left, local posterior left, and interhemispheric regions. Maximum diagnostic accuracies with leave-one-out cross-validation were 77.27% for subject-based classification and 78.25% for epoch-based classification. These findings suggest not only that EEGs from AD patients are less complex than those from controls, but also that the richness of the information contained in pairs of EEGs from patients is also lower than in age-matched controls. The analysis of EEGs in AD with dLZC may increase the insight into brain dysfunction, providing complementary information to that obtained with other complexity and synchrony methods.

1. Introduction

Alzheimer’s disease (AD) is the most prevalent form of dementia in the world [1,2]. Symptoms include progressive memory, cognitive, and behavioural changes before death, caused by amyloid plaques and hyperphosphorated tau in the brain. The cause of AD is currently unknown [3] and many theories have been suggested. These include the amyloid cascade hypothesis [3,4], which suggests remaining amyloid β, a protein produced during cell metabolism and then usually further broken down, initiates AD [5], or that it is a disconnection syndrome [6], which is characterised by the loss of connections between neurones in cortical areas from plaques and cell death [7]. Whatever the cause, it is currently understood that the alteration of information creation and transportation in the brain is what hinders the reaction of an AD patient to surrounding stimuli [8].

The gradual onset of AD and its symptoms is a contributing factor to poor AD diagnosis, a significant problem [9], and the main contributor to the delay of patient diagnosis of up to 4 years from the symptom onset [10]. AD diagnosis is also hampered by frequent syndromic overlap [11]. The current clinical diagnosis is based on the National Institute of Neurological and Communicative Disorders and Stroke and the Alzheimer’s Disease and Related Disorders Association NINCDS-ADRDA criteria [12] and facilitated by medical histories, psychiatric evaluation and tests on a patient’s memory, reasoning and mental state [13], and involving knowledgeable informants other than the patient [14].

AD is a cortical dementia, changing the interaction between neurons in the brain and, as a consequence, the dynamical brain activity. Some of these changes can be captured in electroencephalogram (EEG) recordings [8]. Given this and the portable, non-invasive, and low cost clinical factors of the EEG, this type of signal is seen as a useful research tool in AD. Further research into the ability to measure the impact of AD on the EEG may increase the possibility of clinical use of the EEG in the diagnosis and monitoring of AD in the future. To this end, research in this area is focused on the optimal signal processing method for this particular application.

There is ample evidence of EEG changes in AD patients [15]. The major effects of AD on the EEG that have been observed are slowing, reduction of complexity, and perturbations in EEG synchrony [15]. Slowing of the EEG in AD and Mild Cognitive Impairment (MCI) is associated with an increase of power in low frequency bands delta (0.5–4 Hz) and theta (4–8 Hz) and a decrease of power in the higher frequency bands alpha (8–13 Hz) and beta (13–30 Hz) (for a detailed review, please see [15]). Slowing of the EEG in AD is usually quantified by applying a method based on the Fourier transform, i.e., a linear transform. However, as a result of the non-linear nature of the EEG [16], the use of non-linear analysis methods for the characterisation of this biomedical signal could highlight relevant changes associated with different diseases that might not be detected with conventional linear methods. The reduction of irregularity and complexity of EEG signals in AD is the main finding obtained with non-linear methods [8,15,17]. Last, but not least, EEG signals of patients with AD are generally less synchronous than those from age-matched control subjects [18]. Several methods have been applied to characterise the synchrony changes of EEG signals in AD (a detailed review can be found in [15]), either using local measures (i.e., those establishing relationships between pairs of signals) or global measures (i.e., methods that can be applied to signals from all EEG channels simultaneously) [18].

In spite of the previous findings, there is room for the introduction of novel methods for the analysis of EEG signals in AD. A possibility consists in extending the measure of complexity changes in the EEG with a non-linear method to pairs of signals (bivariate) or more channels recorded simultaneously (multivariate). Lempel–Ziv complexity (LZC) [19] is a popular non-linear method that has been used to characterise changes to the complexity of the EEG in AD [20,21,22]. This univariate method has been shown to be appropriate for the analysis of non-stationary, short data sets [23,24] and does not need the application of arbitrary variables [25]. However, in spite of its ability to highlight changes in complexity in EEG signals, univariate LZC cannot quantify the relationships between the complexities of pairs of electrodes. This has led to the introduction of extensions of the LZC algorithm to bivariate and multivariate contexts [25,26,27].

In this pilot study we introduce a new LZC algorithm based on the concept of distance, the distance-based LZC (dLZC), to estimate the complexity of pairs of signals. We hypothesised that this method would highlight regional differences between EEG signals from AD patients and age-matched control subjects, and that these could be used to classify EEG signals automatically. We also tested the performance of the method with synthetic data.

The outline of the paper is as follows. Section 2 describes the EEG database and introduces dLZC and the synthetic data used to test the method. Results with synthetic data and EEG signals are presented in Section 3, starting with an analysis of the results obtained for different pairs of electrodes and the classification accuracy that could be achieved with it, prior to presenting regional differences. The discussion of results and conclusions from this research follow in Section 4.

2. Materials and Methods

2.1. Subjects and EEG Recording

Twenty-two subjects, 11 patients with a diagnosis of AD (5 men; 6 women; age: 72.5 ± 8.3 years, mean ± standard deviation (SD)) and 11 age-matched controls (7 men; 4 women; age: 72.8 ± 6.1 years, mean ± SD), took part in this pilot study. These subjects were recruited from the Alzheimer’s Patients’ Relatives Association of Valladolid (AFAVA), Valladolid, Spain, and the AD patients fulfilled the criteria of probable AD. Informed consent was obtained for all 22 subjects and the local ethics committee approved the study.

The diagnosis of probable AD was supported by clinical evaluation including clinical history, physical and neurological examination. Brain scans were included, as was a Mini-Mental State Examination (MMSE) to evaluate the level of dementia impact on each subject. The average MMSE score for the AD patients was 13.1 ± 5.9 (mean ± SD). All control subjects had an MMSE score of 30.

EEGs were recorded from each subject at the Hospital Clínico Universitario de Valladolid (Spain) at electrodes F3, F4, F7, F8, Fp1, Fp2, T3, T4, T5, T6, C3, C4, P3, P4, O1, O2, Fz, Cz and Pz of the international 10–20 system. All electrodes were referenced to the linked ear lobes of each subject. Recordings were taken in a resting but awake state, with eyes closed. EEG data were recorded for each subject. EEGs were collected using Profile Study Room 2.3.411 EEG equipment (Oxford Instruments, Oxford, UK). This applied a low-pass hardware filter of 100 Hz before the signals were sampled at 256 Hz and digitised with a 12-bit A-to-D converter.

Artefact-free sections of the EEG signals were selected by Dr Pedro Espino, the specialist neurophysiologist overseeing the recording of the EEGs, and were then copied as ASCII files for analysis offline. Artefacts included movement and noise and in no case electroencephalographic signs of sleep were observed. These epochs were 5 s (1280 data points) in length. On average, 28.0 ± 15.1 epochs (mean ± SD) were selected from each electrode for each subject. The total number of artefact-free epochs analysed was 9849, with 5648 epochs corresponding to AD patients and 4201 epochs corresponding to control subjects.

Before non-linear analysis, all EEGs were filtered in both forward and reverse directions to avoid net phase shift with a Hamming window FIR filter with order 426 and cut-off frequencies at 0.5 Hz and 40 Hz to remove residual artefacts.

2.2. Synthetic Data

Although modelling a signal as the EEG is difficult as a result of the complex nature of this biomedical signal, different efforts have been made. Mathematical models of EEG signals are often represented by a second-order non-linear differential equation; any coupling between two or more signals is also described by a strength parameter, often in the form of a further differential equation [28].

Therefore, to test the performance of dLZC, two coupled dynamical non-linear systems were used: a Rössler–Rössler system (no directionality) and a directed Rössler system driving a Lorenz system, as depicted in [29]. The driver is an autonomous Rössler system with:

$$\begin{gathered} {\dot{x}}_1 = -\mathsf{\alpha }\left\{x_2+x_3\right\} \\ {\dot{x}}_2 = \mathsf{\alpha }\left\{x_1+0.2x_2\right\} \\ {\dot{x}}_3 = \mathsf{\alpha }\left\{0.2+x_3\left(x_1-5.7\right)\right\}, \end{gathered}$$

(1)

which drives a Lorenz system with the coupling strength C = 8:

$$\begin{gathered} {\dot{y}}_1 = 10\left\{-y_1+y_2\right\} \\ {\dot{y}}_2 = 28y_1-y_2-y_1{y}_3+C{x}_2^2 \\ {\dot{y}}_3 = y_1{y}_2-\frac{8}{3}{y}_3, \end{gathered}$$

(2)

These synthetic data, with each oscillator consisting of 5000 data points in length and sampled at 1000 Hz, were obtained from [30]. Coupling values, α, were investigated from no coupling to full coupling, 0 to 1, in equal steps of 0.05.

2.3. Distance-Based Lempel–Ziv Complexity

A distance-based measure can be useful to identify the differences seen between pairs of signals. A true distance measure satisfies three main criteria [26]. If D(x, y) is the distance measure between signals x and y, these criteria can be identified as:

• Non-negative, i.e., D(x, y) ≥ 0;
• Symmetric, i.e., D(x, y) = D(y, x);
• Satisfy the triangle inequality, i.e., D(x, y) ≤ D(x, z) + D(z, y )

By satisfying these three criteria, a distance-based measure makes no prior assumptions as to the path the information takes, and thus the location and timing of any signal similarities, around the brain.

This concept was used in [26] to introduce bivariate distance measures based on LZC. As well as successfully applying all five measures to construct a phylogenic tree based on mitochondrial DNA with only one misplacement, four of the five measures were also mathematically proven as distance measures within an appendix of [26].

However, we previously showed that there were some problems with the normalisation applied in the distances introduced by Otu and Sayood [26] when using them for the analysis of EEG signals in AD [31]. Therefore, the introduction of a new distance-based metric based on LZC is needed.

LZC complexity is based on the symbolisation of the original time series. This involves converting the original time series into a discrete sequence with a finite number of symbols in a coarse-graining stage. In this pilot study the EEGs were converted into binary sequences using the median as the threshold T_d. In this coarse-graining step, a sequence P = s(1), s(2), …, s(n) is created by comparing the samples from the original sampled signal x(i) with the threshold, with s(i) given by:

$$s\left(i\right) = \{\begin{array}{c}0 if x\left(i\right)<T_d\\ 1 if x\left(i\right)\ge T_d\end{array}$$

(3)

To compute the LZC from this binary sequence, P has to be scanned from left to right and a complexity counter is increased every time a new subsequence is found. A detailed description of the LZC parsing algorithm can be found in [32].

The aforementioned complexity algorithm would return a complexity value that is dependent on the length of the sequence being scanned. Therefore, the complexity counter must be normalised against its upper bound to create comparable results [19]. For a binary sequence of length n, this upper bound is [33]:

$$b\left(n\right) = \frac{n}{lo{g}_2\left(n\right)}$$

(4)

Thus, LZC can be calculated as follows:

$$C\left(n\right) = \frac{c\left(n\right)lo{g}_2\left(n\right)}{n}$$

(5)

In order to extend the concept of LZC to pairs of signals, we introduce dLZC. If a signal x(n) is coarse-grained to form a binary sequence P and signal y(n) to form a binary sequence Q, dLZC can be computed as follows:

$$dLZC\left(x,y\right) = \frac{c\left(PQ\right)-c\left(PP\right)+c\left(QP\right)-c\left(QQ\right)}{b\left(2n\right)}$$

(6)

where c(PQ) denotes the complexity counter for the concatenation of P and Q, c(QP) denotes the complexity counter for the concatenation of Q and P, c(PP) is the complexity counter for the concatenation of P and P, c(QQ) is the complexity counter for the concatenation of Q and Q, and the normalisation takes into account that the concatenation duplicates the length of the signals.

The dLZC of signal pairs with few sub-sequences in common would be higher than in signal pairs with a large percentage of sub-sequences in common. Therefore, dLZC measures how dissimilarly complex two signals might be: dLZC for two complex signals with similar complexity (i.e., characterised by a high LZC complexity value but arising from similar sub-sequences) would be lower than dLZC for two complex signals with their high complexities arising from different sub-sequences.

In order to evaluate the dissimilarity in complexity of EEG signals over local and remote distances, a subset of pairs of electrodes was chosen. Local pairs focused on the local anterior (Fp1-F7, Fp2-F8, Fp1-F3, Fp2-F4, Fp1-C3, Fp2-C4, F7-C3, F8-C4, F3-C3 and F4-C4) and the local posterior (O1-P3, O2-P4, O1-T5, O2-T6, O1-C3, O2-C4, P3-C3, P4-C4, T5-C3 and T6-C4) regions, while distant pairs spanned the central line (Fp1-O1, Fp2-O2, F7-O1, F8-O2, F3-O1, F4-O2, Fp1-P3, Fp2-P4, F7-P3, F8-P4, F3-P3, F4-P4, Fp1-T5, Fp2-T6, F7-T5, F8-T6, F3-T5 and F4-T6). The interhemispheric dLZC was also estimated between all pairs of interhemispheric electrodes. These pairs of electrodes have been previously used in the non-linear analysis of EEG signals of AD patients [34].

2.4. Statistical Analysis

For the dLZC results from the EEG database, a Lilliefors test was applied to investigate the distribution of the dLZC results, and a Bartlett or Levene test, chosen upon the results of the Lilliefors test, was applied to analyse homoscedascity. A Student’s t-test or Kruskal–Wallis tests were also applied to results to evaluate the statistical significance of differences between individual electrode or region pairs. In all the above statistical analysis, statistical significance was set at p < 0.01 [35].

Statistically significant electrode pairs were then further analysed using Receiver Operating Characteristic (ROC) curves and Leave-One-Out (LOO) cross-validation analysis. ROC curves are a measure for observing the classification performance of a given method and hypothesis. It provides results of sensitivity, i.e., true positives, specificity, i.e., true negatives, and accuracy, i.e., both true positives and true negatives [36].

In this pilot study, both subject-based LOO cross-validation and epoch-based LOO cross-validation were applied. In the first, all results from one subject were removed and the analysis was run on a dataset of 21 subjects; this was then used to classify the results from the removed subject and this was compared to the correct result. This was repeated for all subjects. For epoch-based LOO cross-validation, this method was amended to removing one epoch from one subject at each test. Therefore, sensitivity would either correspond to the percentage of AD patients or EEG epochs from AD patients correctly classified, specificity would either correspond to the percentage of control subjects or EEG epochs from control subjects correctly identified, and accuracy would represent the percentage of total subjects or EEG epochs correctly identified as corresponding to AD or a control.

Furthermore, dLZC results were grouped into 7 different groups corresponding to right local anterior, left local anterior, right local posterior, left local posterior, right distant, left distant, and interhemispheric regions, and a two-way analysis of variance (ANOVA) was chosen to evaluate the interactions between electrode or region pairs and the diagnostic groups. As a result of the different number of tests of significance performed, significance was set at p = 0.0071 following a Bonferroni correction of 7.

3. Results

3.1. dLZC of Synthetic Data

The Rössler–Lorenz coupled system was found to have greater dLZC than the Rössler–Rössler coupled system for the same coupling in all cases, as shown in

Table 1. Distance-based Lempel-Ziv Complexity (dLZC) results for differently coupled Rössler–Rössler and Rössler–Lorenz coupled systems.

Coupling	Rössler–Rössler	Rössler–Lorenz
0.0	0.2609	0.2786
0.05	0.2388	0.2698
0.1	0.2123	0.3450
0.15	0.2211	0.3317
0.2	0.2167	0.3892
0.25	0.2433	0.3715
0.3	0.1592	0.4157
0.35	0.2344	0.3406
0.4	0.2477	0.3848
0.45	0.2654	0.4467
0.5	0.2521	0.3715
0.55	0.2433	0.4069
0.6	0.2433	0.3317
0.65	0.2344	0.4202
0.7	0.2521	0.4334
0.75	0.2433	0.3450
0.8	0.2211	0.4025
0.85	0.2433	0.3804
0.9	0.2388	0.3052
0.95	0.2433	0.3582
1.0	0.2521	0.2698

. Furthermore, the range of dLZC values was also greater for the latter. As the level of coupling increases, however, there is not a consitent trend of results for either type of system. Maximum dLZC values were found with 0.7 and 1.0 coupling for the Rössler–Rössler coupled system (no directionality) and 0.45 for the Rössler–Lorenz system. Minimum dLZC values were found with 0.3 coupling for the Rössler-Rössler coupled system and 0.05 and 1.0 coupling for the Rössler system driving a Lorenz system.

3.2. dLZC of EEG Data

To test the stability of dLZC for different signal lengths, an analysis was performed with epoch sizes ranging from 5 to 2560 data points. Figure 1 shows an example of this. Results suggest that dLZC values are stable for epoch sizes similar to those used in this study.

Next, dLZC was computed for the different aforementioned electrode pairs. Figure 2 and Figure 3 summarise the average dLZC values for all electrode pairs for control subjects and AD patients.

The dLZC values were consistently higher for controls than for patients, suggesting that electrode pairs for AD patients are jointly less complex than electrode pairs for age-matched control subjects. The differences between dLZC values from control subjects and AD patients are particularly evident for pairs including electrodes from the occipital, parietal, and temporal regions. The dLZC results were found to be normally distributed and homoscedastic in nature. Statistically significant (p < 0.01, Student’s t-test) differences were seen in 17 electrode pairs, with the distant electrode pair Fp1-P3 being the most statistically significant, p = 0.0016, followed by the distant electrode pair Fp1-O1 (p = 0.0026) and the interhemispheric electrode pair O2-P3 (p = 0.0026).

Figure 4 summarises all electrode pairs for which significant differences between the dLZC values of AD patients and control subjects were found (p < 0.01, Student’s t-test). It can be seen that these differences are more pronounced on the left hemisphere, with no significant differences between electrode pairs for the right local anterior, right local posterior, and right distant electrode pairs.

To ascertain the possible usefulness of dLZC in a diagnostic context, ROC curves with LOO cross-validation were used for subject-based and epoch-based classification and sensitivity (percentage of AD patients or AD patients’ EEG epochs correctly classified), specificity (proportion of control subjects or control subjects’ epochs identified as such by the method), and accuracy (percentage of total subjects or EEG epochs correctly classified) were computed for all electrode pairs highlighted in Figure 4. The optimum threshold for the ROC curves was chosen to be that maximising the accuracy of the classification. The results for subject-based and epoch-based classifications are summarised in

Table 2. Subject-based and epoch-based sensitivity, specificity, and accuracy of the dLZC results for all the electrode pairs where significant differences between AD patients and control subjects were found. Results were computed using leave-one-out (LOO) cross-validation. DL: Distant Left; LPL: Local Posterior Left; I: Interhemispheric.

Region	Electrode Pair	Subject-Based			Epoch-Based
		Sensitivity	Specificity	Accuracy	Sensitivity	Specificity	Accuracy
DL	Fp1-O1	63.64	81.82	72.73	69.97	66.92	68.67
	Fp1-P3	63.64	72.73	68.18	62.89	69.58	65.75
	Fp1-T5	72.73	63.64	68.18	68.84	67.68	68.34
	F3-O1	81.82	72.73	77.27	73.94	63.88	69.64
	F3-P3	72.73	72.73	72.73	61.19	72.24	65.91
LPL	O1-P3	72.73	81.82	77.27	75.35	72.24	74.03
	O1-T5	72.73	81.82	77.27	81.02	68.82	75.81
I	Fp1-O2	72.73	81.82	77.27	77.05	65.40	72.08
	Fp1-P4	63.64	81.82	72.73	62.04	63.12	62.50
	Fp1-T6	63.64	90.91	77.27	63.17	68.44	65.42
	F3-O2	72.73	63.64	68.18	83.85	59.32	73.38
	O1-O2	72.73	63.64	68.18	83.57	71.10	78.25
	O1-P4	72.73	81.82	77.27	78.75	69.20	74.68
	O1-T6	63.64	90.91	77.27	78.47	70.72	75.16
	O2-P3	81.82	54.55	68.18	78.19	69.96	74.68
	O2-T5	81.82	63.64	72.73	75.35	71.10	73.54
	P3-P4	54.55	63.64	59.09	67.14	67.30	67.21

.

The highest accuracy was 77.27% for subject-based classification (a result that was obtained with distant left, local posterior left, and interhemispheric electrode pairs) and 78.25% for epoch-based classification (a result obtained with the interhemispheric electrode pair O1-O2). Sensitivity reached a maximum of 81.82% for subject-based classification (at distant left electrode pair F3-O1 and interhemispheric pairs O2-P3 and O2-T5) and also exceeded 80% for some electrode pairs in epoch-based classification (83.57% at interhemispheric pair O1-O2, 83.85% at interhemispheric pair F3-O2, and 81.02% at local posterior left electrode pair O1-T5). Last, but not least, the maximum specificity was 90.91% for subject-based classification (obtained at interhemispheric electrode pairs including the temporal electrode T6: Fp1-T6 and O1-T6), but did not exceed 72.24% for epoch-based classification (at distant left electrode pair F3-P3 and local posterior left electrode pair O1-P3). These results suggest that some pairs of electrodes could contribute to an improved sensitivity, whilst others have to be considered when trying to maximise the specificity of the method.

Finally, to evaluate the significance of the observed regional changes of dLZC, its values were averaged into seven different regions corresponding to right local anterior, left local anterior, right local posterior, left local posterior, right distant, left distant, and interhemispheric pairs of electrodes.

Table 3. The average values and standard deviations of the local, distant, and interhemispheric dLZC in the AD patients and control subjects. Significant differences are highlighted with an asterisk. LAR: Local Anterior Right; LAL: Local Anterior Left; LPR: Local Posterior Right; LPL: Local Posterior Left; DR: Distant Right; DL: Distant Left; I: Interhemispheric.

Mean ± SD	LAR	LAL	LPR	LPL *	DR	DL *	I
Controls	0.35 ± 0.05	0.36 ± 0.04	0.40 ± 0.05	0.40 ± 0.04	0.37 ± 0.03	0.39 ± 0.04	0.38 ± 0.04
AD patients	0.33 ± 0.05	0.32 ± 0.05	0.34 ± 0.06	0.33 ± 0.07	0.33 ± 0.05	0.32 ± 0.05	0.34 ± 0.05

summarises the results, showing that significant differences (p < 0.0071) were found for the local posterior left and distant left regions, but not for the rest. This suggests that the averaging of dLZC values limits the potential identification of differences between groups at some regions, as Table 2 shows that differences between AD patients and control subjects could be found at some interhemispheric electrode pairs. ANOVA analysis with the independent variable of diagnosis shows statistically significant differences for both diagnosis and electrode pairs with no significant interaction (diagnosis F = 389.38, df = 1, p = 2.00 × 10⁻⁸⁰, electrode pairs F = 3.13, df = 119, p = 2.82 × 10⁻²⁵, interaction F = 0.6805, df = 119, p = 0.9965). With mean results for region analysis, only diagnosis was found to be statistically significant (diagnosis F = 38.26, df = 1, p = 6.42 × 10⁻⁹, region F = 1.3778, df = 6, p = 0.2276, interaction F = 0.6229, df = 6, p = 0.7117).

Table 4. Subject-based and epoch-based sensitivity, specificity, and accuracy of the dLZC results averaged in regions. Only results for regions where significant differences between AD patients and control subjects were found are shown. Results were computed using LOO cross-validation. LPL: Local Posterior Left; DL: Distant Left.

Region	Subject-Based			Epoch-Based
	Sensitivity	Specificity	Accuracy	Sensitivity	Specificity	Accuracy
LPL	54.55	63.64	59.09	74.22	69.96	72.40
DL	72.73	63.64	68.18	67.42	66.54	67.05

shows the classification results obtained with the averaged dLZC values for those regions where significant differences were found. It can be seen that accuracies, sensitivities, and specificities are, in most cases, significantly lower than when considering the electrode pairs separately.

4. Discussion and Conclusions

In this pilot study, a new non-linear signal processing metric, dLZC, was introduced and used in the characterisation of resting state EEG activity of 11 AD patients and 11 control subjects. This new metric consists in modifying the well-known LZC algorithm [19] and applying it to pairs of signals, and satisfies the criteria for the mathematical definition of distance [26]. In that way, the method does not reflect any directional trends in the data (i.e., dLZC(x, y) = dLZC(y, x)), but the overall complexity of pairs of signals. For this reason it is, therefore, particularly appropriate for the analysis of resting state EEG signals. With dLZC, the concept of algorithmic complexity is extended to pairs of signals. The dLZC of signal pairs would be higher when complexity in each signal arises from different sub-sequences than when similar sub-sequences are present in each signal. Therefore, for dLZC to be high, not only the complexity of each separate signal needs to be high, but their high complexities also need to be resulting from different sub-sequences in each signal.

The dLZC values for AD patients were lower than for age-matched control subjects for most electrode pairs, although statistically significant differences were only found in electrode pairs in the distant left (Fp1-O1, Fp1-P3, Fp1-T5, F3-O1, F3-P3), local posterior left (O1-P3, O1-T5), and interhemispheric regions (Fp1-O2, Fp1-P4, Fp1-T6, F3-O2, O1-O2, O1-P4, O1-T6, O2-P3, O2-T5, P3-P4). The range of dLZC values for both subject groups was similar to that corresponding to a Rössler-Lorenz coupled system, but was higher than for a Rössler-Rössler coupled system, suggesting that a degree of complex coupling is present in EEG signals.

The possible diagnostic value of dLZC was assessed using ROC curves with LOO cross-validation in those electrode pairs where dLZC values were significantly different between AD patients and control subjects. With a subject-based classification scheme, the highest accuracy was 77.27% at different electrode pairs in the distant left, local posterior left, and interhemispheric regions; accuracy was slightly better (78.25%) using an epoch-based classification. It is worth noting that the highest sensitivity values were obtained using an epoch-based classification (83.85% at interhemispheric pair F3-O2 vs. maximum subject-based classification sensitivities of 81.82% at electrode pairs F3-O1, O2-P3 and O2-T5). On the other hand, specificity was significantly higher for subject-based classification (90.91% at interhemispheric electrode pairs Fp1-T6 and O1-T6 vs. maximum specificity of 72.24% for epoch-based classification at electrode pairs F3-P3 and O1-P3). Therefore, electrode pairs need to be carefully chosen; interhemispheric pairs including T6 might lead to a high specificity but not necessarily a high sensitivity, which improves when O2 is part of the electrode pair being considered. It should be noted that dLZC did not highlight any group differences between electrode pairs for the right local anterior, right local posterior, and right distant electrodes.

To minimise the number of comparisons, dLZC values were averaged in seven different regions [34] corresponding to right local anterior, left local anterior, right local posterior, left local posterior, right distant, left distant, and interhemispheric electrode pairs. Classification results were notably worse using the averaged dLZC values. In particular, the statistically significant differences for the interhemispheric pairs reported in Table 2 disappeared when combining all electrodes. This suggests that local measures (i.e., those establishing relationships between pairs of signals) are useful to highlight differences related to changes to brain activity in AD patients that might not be detected with a more global, region-based approach.

This same database has been previously analysed with different univariate (i.e., methods analysing electrodes separately rather than electrode pairs) non-linear methods well-suited to the characterisation of short and noisy biomedical signals. In particular, a significantly reduced LZC (p < 0.01, Student’s t-test) was found at electrodes T5, P3, P4 and O1 in AD patients with a 3 symbol coarse-graining and at P3 and O1 with a 2 symbol coarse-graining similar to that used in this study, with subject-based classification accuracies—without LOO cross-validation procedure—between 72.73% and 81.82% [20]. These electrodes are among those part of the electrode pairs for which dLZC highlights significant differences between AD patients and age-matched control subjects. This is in agreement with the interpretation of this novel metric as a measure of how similarly or dissimilarly complex two signals might be, with higher dLZC associated with pairs of complex signals with dissimilar complexity. However, it is worth noting that LZC failed to identify any significant differences between both groups at Fp1, F3, or T6. On the other hand, significant differences were found between AD patients and control subjects at electrodes T5, T6, P3, P4, O1 and O2 (p < 0.01, Student’s t-test) using the rate of decrease of auto-mutual information (AMI), an information theory method [37]. Subject-based classification accuracies—without LOO cross-validation procedure—for the rate of decrease of AMI ranged from 81.82% to 90.91% [37]. This method has been interpreted as a measure of the degree of complexity in time series [34], so finding significant differences at T6 would be in agreement with the interpretation of dLZC as a measure of complexity for pairs of signals. Last, but not least, complexity in this database has also been characterised with multiscale entropy (MSE) [38]. Significant differences between the MSE of the EEG on large time scales of AD patients and controls (p < 0.01, Student’s t-test) were found at F3, F7, Fp1, Fp2, T5, T6, P3, P4, O1, and O2, with subject-based classification accuracies—without LOO cross-validation—between 77.27% and 90.91% [39]. Recently introduced extensions of MSE also support the notion of decreased complexity in certain areas of the brain in AD patients with the same database used in this study [40]. Therefore, although a comparison between univariate methods and dLZC is not straightforward, previous results support the loss of complexity at some electrodes that are part of the electrode pairs in which significant differences between groups were found with dLZC. This is also in agreement with the decrease of physiological complexity with disease [41].

Table 5. Subject-based and epoch-based sensitivity, specificity, and accuracy for all the electrodes where significant differences between AD patients and control subjects were found with a selection of other relevant non-linear methods previously used in the analysis of the same electroencephalogram database. NR: not reported; * denotes the studies in which LOO was used.

Method	Electrode	Subject-Based			Epoch-Based
		Sensitivity	Specificity	Accuracy	Sensitivity	Specificity	Accuracy
Sample Entropy (SampEn) (m = 1, r = 0.25) [42]	P3	72.73	81.82	77.27	NR	NR	NR
	P4	63.64	90.91	77.27	NR	NR	NR
	O1	81.82	72.73	77.27	NR	NR	NR
	O2	90.91	63.64	77.27	NR	NR	NR
Lempel-Ziv Complexity (LZC) (3 symbol conversion) [20]	T5	72.73	72.73	72.73	NR	NR	NR
	P3	81.82	81.82	81.82	NR	NR	NR
	P4	72.73	90.91	81.82	NR	NR	NR
	O1	90.91	72.73	81.82	NR	NR	NR
Slope of Multiscale Entropy (MSE) (m = 1, r = 0.25, 12 scales) for large time scales [39]	F3	81.82	81.82	81.82	NR	NR	NR
	F7	81.82	72.73	77.27	NR	NR	NR
	Fp1	90.91	90.91	90.91	NR	NR	NR
	Fp2	100	72.73	86.36	NR	NR	NR
	T5	90.91	81.82	86.36	NR	NR	NR
	T6	81.82	81.82	81.82	NR	NR	NR
	P3	81.82	90.91	86.36	NR	NR	NR
	P4	72.73	90.91	81.82	NR	NR	NR
	O1	81.82	90.91	86.36	NR	NR	NR
	O2	81.82	81.82	81.82	NR	NR	NR
Approximate Entropy (ApEn) (m = 1, r = 0.25) [37]	P3	72.73	81.82	77.27	NR	NR	NR
	P4	63.64	81.82	72.73	NR	NR	NR
	O1	81.82	72.73	77.27	NR	NR	NR
	O2	90.91	63.64	77.27	NR	NR	NR
Auto-Mutual Information (AMI) rate of decrease [37]	T5	90.91	72.73	81.82	NR	NR	NR
	T6	81.82	81.82	81.82	NR	NR	NR
	P3	100.00	81.82	90.91	NR	NR	NR
	P4	81.82	81.82	81.82	NR	NR	NR
	O1	81.82	81.82	81.82	NR	NR	NR
	O2	81.82	81.82	81.82	NR	NR	NR
* Detrended Fluctuation Analysis (DFA) (α2) [43]	T5	54.55	81.82	68.18	54.05	85.19	69.10
	T6	72.73	72.73	72.73	60.98	79.50	69.91
	O1	54.55	72.73	63.64	60.98	81.71	71.07

summarises the most significant results obtained with this database using other non-linear methods, such as entropies, like Sample Entropy (SampEn) [42], Approximate Entropy (ApEn) [37], and MSE [39], metrics correlated with entropy, like the rate of decrease of the AMI [37], LZC [20], and Detrended Fluctuation Analysis (DFA) [43], a method providing an estimation of scaling information and long-range correlations in time series. Nevertheless, it should be mentioned that all these studies did not characterise joint properties of pairs of electrodes, but rather focused on analysing each electrode separately and that, in most cases, the classification results did not include LOO or epoch-based classifications and might, therefore, be overestimating the diagnostic accuracies of univariate methods such as SampEn, ApEn, LZC, MSE, or AMI.

Even though a significant body of work exists measuring the changes in the EEG of AD patients with local measures (i.e., those measuring some type of relationship between signals recorded at pairs of electrodes) showing a decrease in synchrony in AD [18], a comparison between studies is not as simple as a result of the different databases and recording conditions. The most frequently applied linear measures are magnitude and phase coherences, and decreased coherences in AD and MCI patients in comparison to controls have often been found (see [15] for a review of some of these studies). Coherence has been used in conjunction with graph theory as well, achieving a LOO cross-validation accuracy of 93.8% between AD patients and controls [44]. Recently, the bispectral index was applied to a 16 channel EEG, averaged to five regions. This achieved maximum significance of p = 0.0004 in the two temporal regions, F7, T3 and T5, and F8, T4 and T6 with the weighted centre, while the central parietal region, C3, C4, P3 and P4, was found not to be significant [45]. Wavelet coherence has also been used in the analysis of differences between AD patients and control subjects, with statistically significant differences found in the 0–4 Hz and 4–8 Hz bands [46]. Increased coherence in intrahemispheric connections was found with phase lag index (PLI), while interhemispheric connections were increased in AD patients’ EEGs with phase coherence and decreased with PLI [47].

Information theory methods have also been used to characterise the relationships between electrode pairs in AD. Reduced cross-mutual information within the EEGs of AD patients has been identified in the frontal and anterior temporal regions when compared against age-matched control subjects [34]. Significant decreases of mutual information for AD patients in comparison to controls have also been found at electrodes Fp1, Fp2, T3 and T4, indicating a lack of information transmission in these areas [48]. Furthermore, reduced frontal to left temporal and increased left temporal to frontal and occipital to left central entropies with an accuracy of 93.8% were seen between AD patients and control subjects with transfer entropy [49], while Sugihara causality analysis achieved an overall accuracy after a three-way classification of 97.9% [50]. Nevertheless, although it is not straightforward to compare our results with previous findings, the decrease of dLZC in AD is consistent with reported losses of average EEG complexity and synchrony in this type of dementia.

The possible neurophysiological implications of the reduction of dLZC in the EEG of AD patients are not completely clear. It has been hypothesised that decreased EEG complexity in AD might be caused by neuronal death, a general effect of neurotransmitter deficiency, and/or loss of connectivity of local neural networks as a result of nerve cell death [8]. The decrease of joint complexity in electrode pairs observed in AD with dLZC is consistent with the view of AD as a disconnection syndrome, where the loss of afferent and efferent neuron connections destroys effective communication throughout the brain, thus producing the range of AD symptoms commonly seen [6]. This disconnection could, therefore, alter the joint complexity of signals recorded simultaneously at different electrodes.

In spite of these promising results, some limitations of our study merit consideration. First of all, the sample size (11 AD patients and 11 control subjects) is small and leads this to be a pilot study. Although LOO cross-validation techniques have been used to minimise the bias in the subject-based and epoch-based classification, and the latter addresses the issue of the small number of subjects by considering individual epochs rather than subjects in the classification, the sample size might also have had an impact on the classification results. Therefore, further research is needed with a greater number of AD patients and controls to assess the possible clinical usefulness of dLZC. Another limitation arises from the fact that EEG dLZC values might be affected by brain events other than changes of joint complexity in resting state, by volume conduction (active sources in a particular area of the brain might affect different electrodes across the scalp), or recording choices like reference electrodes. The latter could obviously be mitigated by always using the same reference electrodes and by basing the analysis on the differences between populations rather than absolute dLZC values. In addition, the decrease of dLZC observed in the EEG of AD patients might not be exclusive to this pathology. To ascertain the possible use of the method in the context of AD diagnosis, further studies on patients with MCI and other forms of dementia than AD are needed. Last, but not least, potential future studies would include a more in-depth analysis of dLZC in the context of signal processing, a comparison with other methods measuring dependencies between pairs of signals, and a study on the effects of volume conduction on dLZC results.

In summary, dLZC was introduced in this study as a measure of the relationships between pairs of signals and was used in the characterisation of changes in resting state EEG in AD. This novel metric measures how dissimilarly complex two signals might be: the dLZC value for two signals with each having a high value of LZC arising from a similar set of sub-sequences would be lower than that of signals that would have high LZC values but arising from different sets of sub-sequences. As a result of this, dLZC would allow for capturing subtle differences in complexity between pairs of time series; this would make it possible to analyse dependencies between pairs of signals in a novel way, providing information that might not be detected with conventional synchrony metrics. Results showed that dLZC is consistently higher for controls than for AD patients, suggesting not only that EEG signals from AD patients are less complex than those from controls, but also that the richness of the information contained in pairs of EEG signals from patients is also lower than in age-matched controls. The analysis of EEG signals in AD with dLZC may increase the insight into brain dysfunction in this dementia and complement the information obtained with other complexity and synchrony techniques.