Diminished EEG habituation to novel events effectively classifies Parkinson's patients.

OBJECTIVES: We aimed to test if EEG responses to novel events reliably dissociated individuals with Parkinson's disease and controls, and if this dissociation was sensitive and specific enough to be a candidate biomarker of cognitive dysfunction in Parkinson's disease. METHODS: Participants included N = 25 individuals with Parkinson's disease and an equal number of well-matched controls. EEG was recorded during a three-stimulus auditory oddball paradigm both ON and OFF medication. RESULTS: While control participants showed reliable EEG habituation to novel events over time, individuals with Parkinson's did not. In the OFF condition, individual differences in habituation correlated with years since diagnosis. Pattern classifiers achieved high sensitivity and specificity in discriminating patients from controls, with a maximum accuracy of 82%. Most importantly, the confidence of the classifier was related to years since diagnosis, and this correlation increased as the time course of differential habituation increasingly distinguished the groups. CONCLUSIONS: These findings identify systemic alteration in an obligatory neural mechanism that may contribute to higher-level cognitive dysfunction in Parkinson's disease. SIGNIFICANCE: These findings suggest that EEG responses to novel events in this rapid, simple, and inexpensive test have tremendous promise for tracking individual trajectories of cognitive dysfunction in Parkinson's disease.

The Patient Repository for EEG Data + Computational Tools (PRED+CT).

Electroencephalographic (EEG) recordings are thought to reflect the network-wide operations of canonical neural computations, making them a uniquely insightful measure of brain function. As evidence of these virtues, numerous candidate biomarkers of different psychiatric and neurological diseases have been advanced. Presumably, we would only need to apply powerful machine-learning methods to validate these ideas and provide novel clinical tools. Yet, the reality of this advancement is more complex: the scale of data required for robust and reliable identification of a clinical biomarker transcends the ability of any single laboratory. To surmount this logistical hurdle, collective action and transparent methods are required. Here we introduce the Patient Repository of EEG Data + Computational Tools (PRED+CT: predictsite.com). The ultimate goal of this project is to host a multitude of available tasks, patient datasets, and analytic tools, facilitating large-scale data mining. We hope that successful completion of this aim will lead to the development of novel EEG biomarkers for differentiating populations of neurological and psychiatric disorders.

HMEC: A Heuristic Algorithm for Individual Haplotyping with Minimum Error Correction.

Haplotype is a pattern of single nucleotide polymorphisms (SNPs) on a single chromosome. Constructing a pair of haplotypes from aligned and overlapping but intermixed and erroneous fragments of the chromosomal sequences is a nontrivial problem. Minimum error correction approach aims to minimize the number of errors to be corrected so that the pair of haplotypes can be constructed through consensus of the fragments. We give a heuristic algorithm (HMEC) that searches through alternative solutions using a gain measure and stops whenever no better solution can be achieved. Time complexity of each iteration is O(m (3) k) for an m × k SNP matrix where m and k are the number of fragments (number of rows) and number of SNP sites (number of columns), respectively, in an SNP matrix. Alternative gain measure is also given to reduce running time. We have compared our algorithm with other methods in terms of accuracy and running time on both simulated and real data, and our extensive experimental results indicate the superiority of our algorithm over others.

Addressing Big Data Time Series: Mining Trillions of Time Series Subsequences Under Dynamic Time Warping.

Most time series data mining algorithms use similarity search as a core subroutine, and thus the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms, including classification, clustering, motif discovery, anomaly detection, and so on. The difficulty of scaling a search to large datasets explains to a great extent why most academic work on time series data mining has plateaued at considering a few millions of time series objects, while much of industry and science sits on billions of time series objects waiting to be explored. In this work we show that by using a combination of four novel ideas we can search and mine massive time series for the first time. We demonstrate the following unintuitive fact: in large datasets we can exactly search under Dynamic Time Warping (DTW) much more quickly than the current state-of-the-art Euclidean distance search algorithms. We demonstrate our work on the largest set of time series experiments ever attempted. In particular, the largest dataset we consider is larger than the combined size of all of the time series datasets considered in all data mining papers ever published. We explain how our ideas allow us to solve higher-level time series data mining problems such as motif discovery and clustering at scales that would otherwise be untenable. Moreover, we show how our ideas allow us to efficiently support the uniform scaling distance measure, a measure whose utility seems to be underappreciated, but which we demonstrate here. In addition to mining massive datasets with up to one trillion datapoints, we will show that our ideas also have implications for real-time monitoring of data streams, allowing us to handle much faster arrival rates and/or use cheaper and lower powered devices than are currently possible.

Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping.

Most time series data mining algorithms use similarity search as a core subroutine, and thus the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms. The difficulty of scaling search to large datasets largely explains why most academic work on time series data mining has plateaued at considering a few millions of time series objects, while much of industry and science sits on billions of time series objects waiting to be explored. In this work we show that by using a combination of four novel ideas we can search and mine truly massive time series for the first time. We demonstrate the following extremely unintuitive fact; in large datasets we can exactly search under DTW much more quickly than the current state-of-the-art Euclidean distance search algorithms. We demonstrate our work on the largest set of time series experiments ever attempted. In particular, the largest dataset we consider is larger than the combined size of all of the time series datasets considered in all data mining papers ever published. We show that our ideas allow us to solve higher-level time series data mining problem such as motif discovery and clustering at scales that would otherwise be untenable. In addition to mining massive datasets, we will show that our ideas also have implications for real-time monitoring of data streams, allowing us to handle much faster arrival rates and/or use cheaper and lower powered devices than are currently possible.

A disk-aware algorithm for time series motif discovery.

Time series motifs are sets of very similar subsequences of a long time series. They are of interest in their own right, and are also used as inputs in several higher-level data mining algorithms including classification, clustering, rule-discovery and summarization. In spite of extensive research in recent years, finding time series motifs exactly in massive databases is an open problem. Previous efforts either found approximate motifs or considered relatively small datasets residing in main memory. In this work, we leverage off previous work on pivot-based indexing to introduce a disk-aware algorithm to find time series motifs exactly in multi-gigabyte databases which contain on the order of tens of millions of time series. We have evaluated our algorithm on datasets from diverse areas including medicine, anthropology, computer networking and image processing and show that we can find interesting and meaningful motifs in datasets that are many orders of magnitude larger than anything considered before.

Exact Discovery of Time Series Motifs.

Time series motifs are pairs of individual time series, or subsequences of a longer time series, which are very similar to each other. As with their discrete analogues in computational biology, this similarity hints at structure which has been conserved for some reason and may therefore be of interest. Since the formalism of time series motifs in 2002, dozens of researchers have used them for diverse applications in many different domains. Because the obvious algorithm for computing motifs is quadratic in the number of items, more than a dozen approximate algorithms to discover motifs have been proposed in the literature. In this work, for the first time, we show a tractable exact algorithm to find time series motifs. As we shall show through extensive experiments, our algorithm is up to three orders of magnitude faster than brute-force search in large datasets. We further show that our algorithm is fast enough to be used as a subroutine in higher level data mining algorithms for anytime classification, near-duplicate detection and summarization, and we consider detailed case studies in domains as diverse as electroencephalograph interpretation and entomological telemetry data mining.