SYSTEMS AND TECHNIQUES FOR SEGMENTATION OF SEQUENTIAL DATA

摘要

An efficient method and associated systems for segmentation of high throughput sequential data, such as genomic datasets. The technique first utilizes dynamic programming to compute the significance for a large number of candidate segments. It then uses tree-based data structures to detect overlapping significant regions and update them simultaneously. Refinement and merging of significant segments are performed at the end to generate the final segmentation.

主权项

1. A method for the segmentation of sequential data comprising the steps of:
providing data representing a sequence of measurements or a set of measurements in a sequential order; selecting a representative set of segments from the data; computing a significance measure for each selected segment; detecting overlap between segments using two data structures, wherein the first data structure ranks segments by their significance measure and the second data structure stores the boundaries of each segment for overlap checking and wherein overlapping segments with a lower significance ranking (higher significance measure) than a highest ranked co-overlapping segment are deleted and all undeleted segments are retained as significant segments; and returning the set of retained significant segments.