# US 2006/0155483 A1 · System and process for validating, aligning and reordering one or more genetic sequence maps using at least one ordered restriction map

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

- Number: US 2006/0155483 A1
- Document ID: US20060155483A1
- Status: Published application
- Kind: A1
- Application number: 10/432,766
- Filed: 2001-09-28
- Published: 2006-07-13
- Earliest claimed: 2000-09-28
- Assignees: Wisconsin Alumni Research Foundation
- Inventors: Marco Antoniotti; Bhubaneswar Mishra; Thomas Anantharaman; Salvatore Paxia; David Schwartz
- Web page: https://patentgrep.com/patent/US20060155483A1

## CPC

- G16B 30/10: Sequence alignment; Homology search
- G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY

## Abstract

A method and system are provided for comparing ordered segments of a first DNA restriction map with ordered segments of a second DNA restriction map to determine a level of accuracy the first DNA map and/or the second DNA map. In particular, the first and second DNA maps can be received (the first DNA map corresponding to a sequence DNA map, and the second DNA map corresponding to a genomic consensus DNA map as provided in an optical DNA map). Then, the accuracy of the first DNA map and/or the second DNA map is validated based on information associated with the first and second DNA maps. In addition, a method and system are provided for aligning a plurality of DNA sequences with a ordered DNA restriction map. The DNA sequences and the DNA map are received (the DNA sequences being fragments of a genome and the DNA map corresponding to a genomic consensus DNA map which relates to an optical ordered DNA map). Then, a level of accuracy of the DNA sequences and the DNA map is obtained based on information associated with the DNA sequences and the DNA map by means of the method and system described above. The locations of the DNA map at which the DNA sequences are capable of being associated with particular segments of the DNA map are located. Furthermore, it is possible to obtain locations of the DNA map (without the validation) by locating an optimal one of the locations for each of the DNA sequences for each of the locations.

## Claims

### Claim 1

A process for comparing ordered segments of a first DNA map with ordered segments of a second DNA map to determine a level of accuracy of at least one of the first DNA map and the second DNA map, comprising the steps of:
a) receiving the first and second DNA maps, the first DNA map corresponding to a sequence DNA map, the second DNA map corresponding to a genomic consensus DNA map as provided in an ordered restriction DNA map; and
b) validating the accuracy of at least one of the first DNA map and the second DNA map based on information associated with the first and second DNA maps.

### Claim 2 (depends on 1)

The process according to claim 1, wherein the validating step comprises determining whether one or more matches exist between ordered segments of the first DNA map and the ordered segments of the second DNA map.

### Claim 3 (depends on 2)

The process according to claim 2, wherein the validating step further comprises obtaining a number of the matches which exist between the segments of the first DNA map and the segments of the second DNA map after the determining substep.

### Claim 4 (depends on 1)

The process according to claim 1, wherein the validating step comprises determining whether the first DNA map includes one or more cuts which are missing from the second DNA map.

### Claim 5 (depends on 4)

The process according to claim 4, wherein the validating step further comprises obtaining a number and locations of the missing cuts, after the determining substep, based on the first and second DNA maps.

### Claim 6 (depends on 1)

The process according to claim 1, wherein the validating step comprises determining whether the second DNA map includes one or more cuts which are absent from the first DNA map.

### Claim 7 (depends on 6)

The process according to claim 6, wherein the validating step further comprises obtaining a number and locations of the absent cuts, after the determining substep, based on the first and second DNA maps.

### Claim 8 (depends on 3)

The process according to claim 3, wherein the validating step further comprises the substeps of:
i. determining whether the first DNA map includes one or more cuts which are missing from the second DNA map,
ii. after substep i, obtaining a first number and locations of the missing cuts based on the first and second DNA maps,
iii. determining whether the second DNA map includes one or more cuts which are absent from the first DNA map, and
iv. after substep iii, obtaining a second number and locations of the absent cuts based on the first and second DNA maps.

### Claim 9 (depends on 8)

The process according to claim 8, further comprising the step of:
c) generating an error indication if at least one of:
i. the number of the matches is less than a match threshold,
ii. the first number of the missing cuts is greater than a first predetermined threshold, and
iii. the second number of the absent cuts is greater than a second predetermined threshold.

### Claim 10 (depends on 1)

The process according to claim 1, wherein the first DNA map is an in-silico ordered restriction map obtained from a DNA sequence.

### Claim 11 (depends on 10)

The process according to claim 10, wherein the first DNA map includes identification data and at least one vector of the segments of the first DNA map.

### Claim 12 (depends on 11)

The process according to claim 11, wherein the at least one vector of the first segments encodes a size of base-pairs of the DNA sequence.

### Claim 13 (depends on 12)

The process according to claim 12, wherein the second DNA map includes identification data and at least one variable-length vector representing its ordered segments.

### Claim 14 (depends on 1)

The process according to claim 1, wherein the second DNA map is a subsequence of a genome-wide ordered restriction map of an optical DNA map.

### Claim 15 (depends on 1)

The process according to claim 1, wherein the validation step comprises determining the accuracy of at least one of the first DNA map and the second DNA map using the following probability density function:
Pr(D|Ĥ(σ,pc,pƒ))
where:
D is the second DNA map,
Ĥ is the first DNA map,
σ is a standard deviation summarizing map-wide standard deviation data,
pc is a probability of a positive cut of a DNA sequence, and
pƒ is a probability of a false-positive cut of the DNA sequence.

### Claim 16 (depends on 1)

The process according to claim 1, wherein the accuracy is validated as a function of an orientation of the first DNA map with respect to an orientation of the second DNA map.

### Claim 17 (depends on 1)

The process according to claim 1, wherein the validation step comprises the substeps of:
i. executing a dynamic programming procedure (“DPP”) on the first and second DNA maps to generate a first table of partial and complete alignment scores, and first auxiliary tables and first data structures to keep track of number and locations of cuts and segment matches,
ii. receiving a third DNA map which is a reverse map of the first DNA map,
iii. executing the DPP on the second and third DNA maps to generate a second table of partial and complete alignment scores, and second auxiliary tables and second data structures to keep track of number and locations of the cuts and the segment matches, and
iv. analyzing the last row of the first table and a last row of the second table to obtain at least one optimum alignment of the first and second DNA maps, and
v. reconstructing at least one of an optimum alignment and sub-optimal alignments using the first and second auxiliary tables and data structures.

### Claim 18 (depends on 1)

The process according to claim 1, wherein the accuracy is validated by matching an extension of a first left end segment of the segments of the first DNA map to at least one of the segments of the second DNA map.

### Claim 19 (depends on 1)

The process according to claim 1, wherein the accuracy is validated by matching an extension of a first right end segment of the segments of the first DNA map to at least one of the segments of the second DNA map.

### Claim 20 (depends on 1)

The process according to claim 1, further comprising the step of:
d) detecting an alignment of the first DNA map with respect to the second DNA map, the alignment being indicative of sequence positions of the segments of the first DNA map along the second DNA map.

### Claim 21

A software system which, when executed on a processing device, configures the processing device to compare segments of a first DNA map with segments of a second DNA map to determine a level of accuracy of at least one or both of the first DNA map and the second DNA map, the software system comprising:
a processing subsystem which, when executed on the processing device, configures the processing device to perform the following steps:
a) receives the first and second DNA maps, the first DNA map corresponding to a sequence DNA map, the second DNA map corresponding to a genomic consensus DNA map as provided in an ordered restriction DNA map, and
b) validates the accuracy of at least one of the first DNA map and the second DNA map based on information associated with the first and second DNA maps.

### Claim 22 (depends on 21)

The software system according to claim 21, wherein, when validating the accuracy, the processing subsystem determines whether one or more matches exists between at least one of the segments of the first DNA map and at least one of the segments of the second DNA map.

### Claim 23 (depends on 22)

The software system according to claim 22, wherein, when validating the accuracy, the processing subsystem obtains a number of the matches which exist between the segments of the first DNA map and the segments of the second DNA map.

### Claim 24 (depends on 21)

The software system according to claim 21, wherein, when validating the accuracy, the processing subsystem determines whether the first DNA map includes one or more cuts which are missing from the second DNA map.

### Claim 25 (depends on 4)

The software system according to claim 4, wherein, when validating the accuracy, the processing subsystem obtains number and location of the missing cuts based on the first and second DNA maps.

### Claim 26 (depends on 21)

The software system according to claim 21, wherein, when validating the accuracy, the processing subsystem determines whether the second DNA map includes one or more cuts which are absent from the first DNA map.

### Claim 27 (depends on 24)

The software system according to claim 24, wherein, when validating the accuracy, the processing subsystem obtains number and location of the absent cuts based on the first and second DNA maps.

### Claim 28 (depends on 23)

The software system according to claim 23, wherein, when validating the accuracy, the processing subsystem:
i. determines whether the first DNA map includes one or more cuts which are missing from the second DNA map,
ii. obtains number and location of the missing cuts based on the first and second DNA maps,
iii. determines whether the second DNA map includes one or cuts which are absent from the first DNA map, and
iv. obtains a second number of the absent cuts based on the first and second DNA maps.

### Claim 29 (depends on 28)

The software system according to claim 28, wherein, when executed on the processing device, the processing subsystem further configures the processing device to generate an error indication if at least one of:
i. the number of the matches is less than a match threshold,
ii. the first number of the missing cuts is greater than a first predetermined threshold, and
iii. the second number of the absent cuts is greater than a second predetermined threshold.

### Claim 30 (depends on 21)

The software system according to claim 21, wherein the first DNA map is an in-silico ordered restriction map obtained from a DNA sequence.

### Claim 31 (depends on 30)

The software system according to claim 30, wherein the first DNA map includes identification data and a variable-length vector of the segments of the first DNA map.

### Claim 32 (depends on 31)

The software system according to claim 31, wherein the vector of the segments of the first DNA map encodes a size of base-pairs of the DNA sequence.

### Claim 33 (depends on 32)

The software system according to claim 32, wherein the second DNA map includes identification data and a variable-length vector of the segments of the second DNA map.

### Claim 34 (depends on 21)

The software system according to claim 21, wherein the second DNA map is a genome-wide ordered restriction map of an optical DNA map.

### Claim 35 (depends on 21)

The software system according to claim 21, wherein, when validating the accuracy, the processing subsystem determines the accuracy of the at least one of the first DNA map and the second DNA map using the following probability density function:
Pr(D|Ĥ(σ,pc,pƒ))
where:
D is the second DNA map,
Ĥ is the first DNA map,
σ is a standard deviation summarizing map-wide standard deviation data,
pc is a probability of a positive cut of a DNA sequence, and
pƒ is a probability of a false-positive cut of the DNA sequence.

### Claim 36 (depends on 21)

The software system according to claim 21, wherein the accuracy is validated as a function of an orientation of the first DNA map with respect to an orientation of the second DNA map.

### Claim 37 (depends on 21)

The software system according to claim 21, wherein, when validating the accuracy, the processing subsystem:
i. executes a dynamic programming procedure (“DPP”) on the first and second DNA maps to generate a first table of partial and complete alignment scores, and first auxiliary tables and data structures to keep track of the number and locations of cuts and segment matches,
ii. receives a third DNA map which is a reverse map of the first DNA map,
iii. executes the DPP on the second and third DNA maps to generate a second table of partial and complete alignment scores, and second auxiliary tables and data structures to keep track of the number and locations of cuts and segment matches,
iv. analyzes a last row of the first table and a last row of the second table to obtain at least one optimum alignment of the first and second DNA maps, and
v. reconstructing at least one of an optimum alignment and sub-optimal alignments using the first and second auxiliary tables and data structures.

### Claim 38 (depends on 21)

The software system according to claim 21, wherein the accuracy is validated by matching an extension of a first left end segment of the segments of the first DNA map to at least one of the segments of the second DNA map.

### Claim 39 (depends on 21)

The software system according to claim 21, wherein the accuracy is validated by matching an extension of a first right end segment of the first DNA map to at least one of the segments of the second DNA map.

### Claim 40 (depends on 21)

The software system according to claim 21, wherein, when executed on the processing device, the processing subsystem further configures the processing device to determine an alignment of the first DNA map with respect to the second DNA map, the alignment being indicative of sequence positions of the first segments along the second DNA map.

### Claim 41

A process for aligning a plurality of DNA sequences with a DNA map, comprising the steps of:
a) receiving the DNA sequences and the DNA map, the DNA sequences being fragments of a genome, the DNA map corresponding to a genomic consensus DNA map which relates to an ordered restriction DNA map;
b) validating a level of accuracy of at least one of the DNA sequences and the DNA map based on information associated with the DNA sequences and the DNA map; and
c) determining locations of the DNA map at which the DNA sequences are capable of being associated with particular segments of the DNA map.

### Claim 42 (depends on 41)

The process according to claim 41, wherein the locations are determined for each of the DNA sequences.

### Claim 43 (depends on 41)

The process according to claim 41, wherein the locations are positions on the DNA map at which the corresponding DNA sequences are anchorable.

### Claim 44 (depends on 41)

The process according to claim 41, wherein the locations define at least one alignment of the DNA sequences with respect to the DNA map.

### Claim 45 (depends on 44)

The process according to claim 44, wherein the at least one alignment includes multiple alignments of the DNA sequences with respect to the DNA map.

### Claim 46 (depends on 45)

The process according to claim 45, further comprising the step of:
d) ranking the multiple alignments based on a predetermined criteria to obtain a score set which includes a particular score for each of the multiple alignments.

### Claim 47 (depends on 46)

The process according to claim 46, wherein the determining step comprises:
i. providing the DNA sequences in a first order of the multiple alignments with respect to the DNA map, and
ii. determining a position for each of the DNA sequences, with respect to the DNA map, by selecting the DNA sequences to be in a second order corresponding to the score set.

### Claim 48 (depends on 41)

The process according to claim 41, wherein the determining step comprises restricting each of the DNA sequences to be associated with only one of the locations on the DNA map.

### Claim 49 (depends on 48)

The process according to claim 48, wherein the determining step produces a single alignment of the DNA sequences with respect to the DNA map.

### Claim 50 (depends on 41)

The process according to claim 41, wherein the determining step includes:
i. locating an optimal one of the locations for each of the DNA sequences to obtain an alignment solution, and
ii. repeating substep ii for each of the locations.

### Claim 51 (depends on 50)

The process according to claim 50, wherein the locating substep is repeated for each subsequent one of the locations and excluding the alignment solution from a preceding locating substep.

### Claim 52 (depends on 51)

The process according to claim 51, wherein each subsequent locating substep is performed by relaxing at least one particular constraint to determine the respective locations.

### Claim 53 (depends on 52)

The process according to claim 52, wherein the at least one particular constraint includes a first requirement that two of the DNA sequences are prevented from overlapping when associated with the respective locations on the DNA map.

### Claim 54 (depends on 52)

The process according to claim 52, wherein the particular constraint includes at least one of:
i. a second requirement that a maximum number of the DNA sequences are associated with the respective locations on the DNA map, and
ii. a third requirement that an overall score of the alignment of the DNA sequences with respect to the locations on the DNA map is minimized or maximized.

### Claim 55 (depends on 54)

The process according to claim 54, further comprising the step of:
e) assigning respective weighs to the second requirement and the third requirement.

### Claim 56 (depends on 41)

The process according to claim 41, wherein the ordered restriction DNA map is an optical DNA map.

### Claim 57

A software system which, when executed on a processing device, configures the processing device to align a plurality of DNA sequences with a DNA map, the software system comprising:
a processing subsystem which, when executed on the processing device, configures the processing device to perform the following steps:
a) receives the DNA sequences and the DNA map, the DNA sequences being fragments of a genome, the DNA map corresponding to a genomic consensus DNA map which relates to an ordered restriction DNA map,
b) validates a level of accuracy of at least one of the DNA sequences and the DNA map based on information associated with the DNA sequences and the DNA map, and
c) determines locations of the DNA map at which the DNA sequences are capable of being associated with particular segments of the DNA map.

### Claim 58 (depends on 57)

The software system according to claim 57, wherein the locations are determined for each of the DNA sequences.

### Claim 59 (depends on 57)

The software system according to claim 57, wherein the locations are positions on the DNA map at which the corresponding DNA sequences are anchorable.

### Claim 60 (depends on 57)

The software system according to claim 57, wherein the locations define at least one alignment of the DNA sequences with respect to the DNA map.

### Claim 61 (depends on 60)

The software system according to claim 60, wherein the at least one alignment includes multiple alignments of the DNA sequences with respect to the DNA map.

### Claim 62 (depends on 61)

The software system according to claim 61, wherein the processing subsystem, when executed on the processing device, configures the processing device to rank the multiple alignments based on a predetermined criteria to obtain a score set which includes a particular score for each of the multiple alignments.

### Claim 63 (depends on 62)

The software system according to claim 62, wherein the processing device is configured by the processing subsystem to determine the locations of the DNA sequences by:
i. providing the DNA sequences in a first order of the multiple alignments with respect to the DNA map, and
ii. determining a position for each of the DNA sequences, with respect to the DNA map, by selecting the DNA sequences to be in a second order corresponding to the score set.

### Claim 64 (depends on 57)

The software system according to claim 57, wherein the processing device is configured by the processing subsystem to determine the locations on the DNA sequences by restricting each of the DNA sequences to be associated with only one of the locations of the DNA map.

### Claim 65 (depends on 64)

The software system according to claim 64, wherein the processing device is configured by the processing subsystem to determine the locations of the DNA sequences for producing a single alignment of the DNA sequences with respect to the DNA map.

### Claim 66 (depends on 57)

The software system according to claim 57, wherein the processing device is configured by the processing subsystem to determine the locations of the DNA sequences by:
i. locating an optimal one of the locations for each of the DNA sequences to obtain an alignment solution, and
ii. repeating substep ii for each of the locations.

### Claim 67 (depends on 66)

The software system according to claim 66, wherein the locating of the optimal one of the locations is repeated for each subsequent one of the locations and the alignment solution is excluded from a preceding locating iteration.

### Claim 68 (depends on 67)

The software system according to claim 67, wherein the processing subsystem configures the processing device to perform each subsequent locating iteration by relaxing at least one particular constraint to determine the respective locations.

### Claim 69 (depends on 68)

The software system according to claim 68, wherein the at least one particular constraint includes a first requirement that two of the DNA sequences are prevented from overlapping when associated with the respective locations on the DNA map.

### Claim 70 (depends on 68)

The software system according to claim 68, wherein the particular constraint includes at least one of:
i. a second requirement that a maximum number of the DNA sequences are associated with the respective locations on the DNA map, and
ii. a third requirement that an overall score of the alignment of the DNA sequences with respect to the locations on the DNA map is minimized or maximized.

### Claim 71 (depends on 70)

The software system according to claim 70, wherein the processing subsystem, when executed on the processing device, configures the processing device to assign respective weighs to the second requirement and the third requirement.

### Claim 72 (depends on 70)

The software system according to claim 70, wherein the ordered restriction DNA map is an optical DNA map.

### Claim 73

A process for aligning a plurality of DNA sequences with a DNA map, comprising the steps of:
a) receiving the DNA sequences and the DNA map, the DNA sequences being fragments of a genome, the DNA map corresponding to a genomic consensus DNA map which relates to an ordered restriction DNA map; and
b) determining locations of the DNA map at which the DNA sequences are capable of being associated with particular segments of the DNA map, the locations of the DNA sequences being determined by:
i. locating an optimal one of the locations for each of the DNA sequences, and
ii. repeating substep i for each of the locations.

### Claim 74

A software system which, when executed on a processing device, configures the processing device to align a plurality of DNA sequences with a DNA map, the software system comprising:
a processing subsystem which, when executed on the processing device, configures the processing device to perform the following steps:
a) receives the DNA sequences and the DNA map, the DNA sequences being fragments of a genome, the DNA map corresponding to a genomic consensus DNA map which relates to an ordered restriction DNA map, and
b) determines locations of the DNA map at which the DNA sequences are capable of being associated with particular segments of the DNA map by:
i. locating an optimal one of the locations for each of the DNA sequences, and
ii. repeating the locating of the optimal one of the locations for each of the locations.
