# US 2018/0322218 A1 · Determining enhanced longest common subsequences

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0322218 A1
- Document ID: US20180322218A1
- Status: Published application
- Kind: A1
- Application number: 15/587,979
- Filed: 2017-05-05
- Published: 2018-11-08
- Earliest claimed: 2017-05-05
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Lei KOU; Zhongyuan LI
- Web page: https://patentgrep.com/patent/US20180322218A1

## CPC

- G06F 16/90344: {by using string matching techniques}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Enhanced longest common subsequence techniques are provided to improve efficiency and accuracy of any process that uses long sequences. Two superscale data sequences are received. Each data sequence is divided into a set of segments based on one or more heuristics or user input. From the sets of segments, pairs of segments are selected and processed using any longest common subsequence algorithm to determine the longest common subsequence for each pair of segments. The results of the processing are merged to determine the enhanced longest subsequence which is the longest common subsequence for the received superscale data sequences. Dividing the superscale data sequences into segments allows for parallel processing of each segment pair, which results in a faster completion time than prior art methods for determining longest common subsequences.

## Claims

### Claim 1

A system for determining longest common subsequences in super-scale sequences using parallel processing, the system comprising:
at least one computing device; and
an enhanced longest common subsequence (ELCS) engine adapted to:
receive a first sequence;
receive a second sequence;
divide the first sequence into a first set of segments and the second sequence into a second set of segments;
for each pair of segments comprising a selected first segment from the first set of segments and a selected second segment from the second set of segments, process the pair of segments to generate segment data, wherein the segment data includes a longest common subsequence of the pair of segments;
merge the segment data from each of the pairs of segments; and
determine a longest common subsequence of the first sequence and the second sequence based on the merged segment data.

### Claim 2 (depends on 1)

The system of claim 1, wherein the ELCS engine is further adapted to provide the longest common subsequence of the first sequence and the second sequence.

### Claim 3 (depends on 1)

The system of claim 1, wherein the ELCS engine is further adapted to provide a length of the longest common subsequence of the first sequence and the second sequence.

### Claim 4 (depends on 1)

The system of claim 1, wherein the ELCS engine adapted to divide the first sequence into the first set of segments and the second sequence into the second set of segments comprises the ELCS engine adapted to divide the first sequence into the first set of segments and the second sequence into the second set of segments using one or more heuristics.

### Claim 5 (depends on 1)

The system of claim 1, wherein the ELCS engine adapted to divide the first sequence into the first set of segments and the second sequence into the second set of segments comprises the ELCS engine adapted to:
determine unique subsequences in the first sequence and the second sequence; and
divide the first sequence into the first set of segments and the second sequence into the second set of segments based on the determined unique subsequences.

### Claim 6 (depends on 1)

The system of claim 1, wherein the ELCS engine adapted to process the pair of segments to generate segment data comprises the ELCS engine adapted to process the pair of segments using Hirschberg's algorithm or the string-to-string correction problem.

### Claim 7 (depends on 1)

The system of claim 1, wherein the segment data further includes a length of a longest common subsequence of the pair of segments.

### Claim 8 (depends on 1)

The system of claim 1, wherein each pair of segments is processed in parallel.

### Claim 9 (depends on 1)

The system of claim 1, wherein the first sequence comprises one or more of a log or a DNA sequence.

### Claim 10

A system for determining longest common subsequences in super-scale sequences using parallel processing, the system comprising:
at least one computing device; and
an enhanced longest common subsequence (ELCS) engine adapted to:
receive a first sequence;
receive a second sequence;
receive user input;
divide the first sequence into a first set of segments and the second sequence into a second set of segments according to the user input;
for each pair of segments comprising a selected first segment from the first set of segments and a selected second segment from the second set of segments, process the pair of segments to generate segment data, wherein the segment data includes a length of a longest common subsequence of the pair of segments;
merge the segment data from each of the pairs of segments; and
determine a length of a longest common subsequence of the first sequence and the second sequence based on the merged subsequence data.

### Claim 11 (depends on 10)

The system of claim 10, wherein the ELCS engine is further adapted to provide the determined length of the longest common subsequence of the first sequence and the second sequence.

### Claim 12 (depends on 10)

The system of claim 10, wherein the ELCS engine is further adapted to provide the longest common subsequence of the first sequence and the second sequence.

### Claim 13 (depends on 10)

The system of claim 10, wherein the ELCS engine adapted to process the pair of segments to generate segment data comprises the ELCS engine adapted to process the pair of segments using a longest common substring algorithm.

### Claim 14 (depends on 10)

The system of claim 10, wherein the segment data further includes the longest common subsequence of the pair of segments.

### Claim 15 (depends on 10)

The system of claim 10, wherein each pair of segments is processed in parallel.

### Claim 16 (depends on 10)

The system of claim 10, wherein the first sequence comprises one or more of a log or a DNA sequence.

### Claim 17

A method for determining longest common subsequences in super-scale sequences using parallel processing, the method comprising:
receiving user input by a computing device;
dividing a first sequence into a first set of segments and a second sequence into a second set of segments based on the user input by the computing device;
for each pair of segments comprising a selected first segment from the first set of segments and a selected second segment from the second set of segments, processing the pair of segments to generate segment data, wherein the segment data includes a longest common subsequence of the pair of segments;
merging the segment data from each of the pairs of segments by the computing device;
determining a longest common subsequence of the first sequence and the second sequence based on the merged segment data by the computing device; and
providing the longest common subsequence of the first sequence and the second sequence by the computing device.

### Claim 18 (depends on 17)

The method of claim 17, wherein processing the pair of segments to generate segment data comprises processing the pair of segments using Hirschberg's algorithm or the string-to-string correction problem.

### Claim 19 (depends on 17)

The method of claim 17, wherein the segment data further includes a length of a longest common subsequence of the pair of segments.

### Claim 20 (depends on 17)

The method of claim 17, wherein each pair of segments is processed in parallel.