CN105260395A - Reverse index structure based STR data storage and paternity test sorting comparison method - Google Patents

Abstract

The invention discloses a method for storing STR data based on an inverted index structure and sorting and comparing methods for paternity identification, belonging to the technical field of data storage and processing. The STR data storage based on the inverted index structure and the paternity identification sorting comparison method of the present invention mainly include two aspects: one is the STR data storage method based on the inverted index structure. In different data domains, STR data is stored in an inverted index structure in the data domain; the second is the paternity identification sorting and comparison method, which is based on the inverted index structure of the divided domains, and calculates the genetic relationship between the family search samples and the samples in the database , to achieve fast, stable and reliable online family search.

Description

STR data storage and paternity identification sorting comparison method based on inverted index structure

technical field

The invention belongs to the technical field of data storage and processing, and in particular relates to an inverted index structure-based STR data storage and paternity identification sorting and comparison method.

Background technique

According to incomplete statistics, there are currently about 500,000 family-seekers across the country. Among them, war orphans (Japanese orphans), natural disaster orphans, and trafficked people caused by history, natural disasters, and social problems constitute the main body of family-seekers. . In recent years, with the continuous development of biotechnology, family tracing through genetic technology has become more and more feasible.

Family tracing based on gene technology mainly uses paternity identification technology to detect human genetic markers, and analyzes the blood relationship between suspected parents and children according to genetic laws. DNA is the basic carrier of human genetic information. Human chromosomes are mainly composed of DNA. Each human cell has 22 pairs of autosomal chromosomes and 1 pair of sex chromosomes, a total of 46, which come from the father and mother respectively. Both parents provide their offspring with half of their chromosomes, which are paired with each other after fertilization to form the offspring's chromosomes. Since there are about 3 billion nucleotides in the human body to form the entire chromosome system, and the exchange and combination before the formation of germ cells is random, so no two people have the exact same nucleotide sequence except for identical twins. This is human genetic polymorphism. Although there are genetic polymorphisms, each person's chromosomes must only come from their parents, which is the theoretical basis of DNA paternity testing. At present, the identification technology based on short tandem repeat (STR) is widely used in the process of paternity identification. Due to its characteristics of high sensitivity, high personalization, and complete digitalization, this technology has become a common identification technology in the world. technology. A typical autosomal STR locus data is shown below:

site STR D8S1179 13/14 D21S11 31/32 D7S820 11/12

CSF1PO 10/13 D3S1358 15/16 D5S818 11/13 D13S317 8/12 D16S539 9/12 D2S1338 17/23 D19S433 14/14 wxya 16/18 D12S391 18/21 D18S51 13/13 AMEL X/Y D6S1043 12/19 FGA 22/23

.

At present, the solution to the paternity test problem mostly relies on relational databases to store and compare STR data, so as to realize the determination of the parent-child relationship of sample donors. For a locus, its STR data mainly consists of two numbers, one from the father and the other from the mother. In the detection process, it is assumed that each sample detects 16 loci (including one sex locus). Each sample will have values for both alleles at the same locus. Among the 15 STR loci of two subjects with biological parent-child relationship, the data of each locus requires at least one value to be the same. For this problem, to determine whether there is a parent-child relationship between two individuals, at most 4 comparisons at each locus are required, and at most 60 comparisons are required for 15 loci. When the amount of samples stored in the system gradually increases, the comparison calculation amount will also gradually increase. Therefore, although the storage and comparison methods of relational databases can solve the problem of storage and retrieval of relative databases to a certain extent, due to the characteristics of human STR locus data, it is not suitable to use "table" relational databases. It is stored in the database and affects the comparison efficiency of STR data to a large extent. In addition, there is a possibility of variation in genetic information. Once the STR data is mutated, it will further increase the difficulty of using STR data for family finding and paternity testing.

Contents of the invention

In order to overcome the above-mentioned defects in the prior art, the object of the present invention is to provide a method for storing STR data based on an inverted index structure and sorting and comparing methods for paternity identification, which can effectively improve the robustness and comparison of relative databases Efficiency, and at the same time can effectively guarantee the reliability of the family search results.

The present invention is achieved through the following technical solutions:

The method for storing STR data based on an inverted index structure and sorting and comparing methods for paternity testing disclosed by the present invention comprises the following steps:

1) STR data storage based on inverted index structure

First, preprocess all STR data, organize the STR data set of each sample into a standard format; then, use each site as a data domain, and each data domain will store its own STR data; finally, the STR data is stored as an inverted index;

2) Sorting comparison of paternity based on STR data stored in the form of inverted index

First, preprocess the STR data of the relatives to be searched, and organize the STR data sets of each sample into a standard format; then, compare the STR data of each site in their respective data fields to form the final parent-child Relationship index; finally, determine whether there is a parent-child relationship between the samples. If the parent-child relationship index is higher than a specific value, it is considered that the donor of the candidate sample has a parent-child relationship with the donor of the sample to be found, otherwise, it is considered that there is a parent-child relationship between the two. No parent-child relationship exists.

In step 1), the STR data is preprocessed, and the STR data set of each sample is organized into a standard format, as follows:

Denote the sample data set as X={x ₁ ,x ₂ ,...,x _n };

Among them, x _i represents the STR data of the i-th individual, in, Indicates the name of the jth STR locus, and _vjk indicates the eigenvalue of the STR at locus j on the kth chromosome.

The establishment of the data field in step 1) is as follows:

Traverse the STR data of all samples, establish a set of STR locus names STR _N = {str ₁ ,str ₂ ,...,str _m }, and establish a different data field for each str _i in STR _N , denoted as d _i ;i=1,2...m.

In step 1), store the STR data in the form of an inverted index, traverse the sample data set X, and traverse any x _i :(v _j1 /v _j2 ), if If there is an index of v _j1 in the corresponding data field d _m , then add _xi to the index; if there is no inverted index of v _j1 , build the index and add _xi to the index; for v _j2 Proceed in the same way.

In step 2), the STR data to be found are preprocessed, as follows:

Organize the family searching samples into the following format: y={str _j :(v _j1 /v _j2 )}, where str _j represents the name of the jth STR locus, and v _jk represents the STR at locus j on the kth chromosome eigenvalues of .

The calculation of the parent-child relationship index in step 2) is as follows:

For sample y, traverse str _j : (v _j1 /v _j2 ), if there is a field d _m corresponding to str _j , then obtain the sample sets corresponding to v _j1 and v _j2 indexes, which are recorded as X _j1 and X _j2 respectively;

Take the union of X _j1 and X _j2 , denoted as X _j = X _j1 ∪ X _j2 ;

After obtaining the X _j corresponding to each str _j , calculate the union of X _j Each element in X is a candidate sample;

For each element x _i in X, compute in:

Then q _i is the parent-child relationship index of the candidate sample x _i .

In step 2), it is judged whether there is a parent-child relationship, as follows:

According to q _i , the candidate samples x _i are sorted in descending order. If q _i ≥ θ, it is considered that the donor of the sample y to be searched for relatives has a parent-child relationship with the donor of the candidate sample x _i ; otherwise, it is considered that there is no relationship between the two. Parent-child relationship; among them, θ is the threshold value set in advance by the system, which is the number of loci minus 1.

Compared with the prior art, the present invention has the following beneficial technical effects:

1. Higher query efficiency

Traditional family search databases often use relational databases, and optimize and improve the query efficiency of the system by means of vertical segmentation, establishment of views, and establishment of statistical information. However, the query algorithms of these methods are relatively complicated, and are not easy to be understood by operation and maintenance personnel who lack relevant background knowledge. The present invention sets different data storage domains according to different locus points, and uses inverted index structures in different data domains to store paired STR locus data, which greatly improves the query efficiency of the system.

2. Higher scalability

Traditional relative databases based on relational databases often require relative searchers to use specific genetic loci for detection, which greatly limits the scope of use of relative databases and brings great inconvenience to the majority of relative search users. The present invention has no specific requirements for the gene points of family searching. If the points of the system need to be expanded, only the corresponding data field needs to be added without modifying the basic data structure, which greatly improves the scope of application of the system.

3. Avoid the influence of gene mutation on the effect of paternity test

Genetic mutations are one of the formidable barriers that limit the accuracy of paternity tests in family tracing databases. Due to the existence of genetic variation, the STR locus data between the two generations of parents and children may not necessarily coincide completely. Therefore, when a relational database is used to store STR locus data, the complete matching between STR locus data becomes difficult to operate. , the WHERE condition in the SQL statement is difficult to match precisely, which greatly limits the effect of paternity testing. The present invention utilizes the inverted index structure in different data domains to store STR locus data. When inquiring, it only needs to calculate the parent-child relationship index between samples according to the comparison scores in different data domains to obtain the parent-child relationship index of the sample donor. The possibility of having a blood relationship between them is sorted accordingly, which greatly avoids the influence of gene mutation on the effect of paternity identification. The present invention can effectively improve the robustness and comparison efficiency of the relative search database, and can effectively ensure the reliability of the results.

Description of drawings

Figure 1 is a schematic diagram of the overall framework of the system;

Fig. 2 is the STR locus data storage based on the inverted index structure used in the present invention;

Fig. 3 is the algorithm flowchart of the STR data storage based on the inverted index structure;

Fig. 4 is based on the algorithm flow chart of the parent-child identification sorting comparison of the STR data stored in the manner of inverted index;

Figure 5 and Figure 6 are respectively the data structure when the sample number 00002 is not stored and the data structure after storing the sample number 00002 in the D8S1179 domain;

Figure 7 and Figure 8 are the prototypes of the family searching system designed and implemented according to the principles of the present invention, Figure 7 is the STR data stored based on the inverted index structure, and Figure 8 is the family finding result obtained by the family searching algorithm.

detailed description

The present invention will be further described in detail below in conjunction with specific embodiments, which are explanations of the present invention rather than limitations.

Referring to Fig. 1, the STR data storage and paternity identification sorting method based on the inverted index structure of the present invention mainly includes two aspects: one is the STR data storage method based on the inverted index structure, see Fig. 3, the method will be based on The STR locus selected by the sample establishes different data domains, and stores the STR data in the data domain with an inverted index structure; the second is the paternity identification sorting and comparison method, see Figure 4, this method is based on the inverted index structure of the divided domains , to calculate the genetic relationship between the family search samples and the samples in the database, and realize fast, stable and reliable online family search.

1. STR data storage method based on inverted index structure

The STR data storage method based on the inverted index structure includes the following steps: firstly, all STR data are preprocessed, and the STR data set of each sample is organized into a standard format; then, each site is used as a data domain, Each data field will store its own STR data. Finally, store the STR data in an inverted index. The specific process is shown in Figure 3, specifically:

Step 1: Data preprocessing. The data to be stored is organized into the following form: the sample data set is recorded as X={x ₁ ,x ₂ ,…,x _n }, where x _i represents the STR data of the i-th individual, which can be expressed as in Indicates the name of the jth STR locus, and _vjk indicates the eigenvalue of the STR at locus j on the kth chromosome.

Step 2: Create a data domain. Traverse the STR data of all samples, establish a set of STR locus names STR _N = {str ₁ ,str ₂ ,...,str _m }, and establish a different data domain for each str _i in STR _N , denoted as d _i .

Step 3: Data storage. Traversing the sample data set X, for any x _i , traversing :(v _j1 /v _j2 ), if If there is an index of v _j1 in the corresponding data field d _m , then add _xi to the index; if there is no inverted index of v _j1 , build the index and add _xi to the index. The same method is adopted for v _j2 .

The STR locus data stored using the above method is shown in Figure 2. Among them, D8S1179, D21S11, etc. shown above are the data fields corresponding to the STR loci; the left side of the bottom is the data key corresponding to the data, and the numbers in it represent the STR value; the right side of the bottom is the inverted index list corresponding to the data key , each numerical value represents the ID number of the sample donor. For example, the list corresponding to the STR value 12 contains numbers such as 1, 5, 7, 13, 22, etc., indicating that a certain chromosome of samples 1, 5, 7, 13, and 22 has a value of 12 at the site D3S1358.

2. Paternity identification sorting and comparison method based on inverted index structure

On the basis of the STR data storage method based on the inverted index structure, the data storage structure of the STR loci is obtained as shown in FIG. 2 . When searching for relatives, the paternity ranking and comparison method based on the inverted index structure will be used. This method mainly includes the following steps: First, preprocess the STR data to be searched, and organize the STR data sets of each sample into a standard format; then, compare the STR data of each site in their respective data fields, and form the final parent-child relationship index; finally, determine whether there is a parent-child relationship between the samples, if the parent-child relationship index is higher than a specific value , it is considered that the donor of the candidate sample has a parent-child relationship with the donor of the sample to be traced, otherwise it is considered that there is no parent-child relationship between the two.

Step 1: Data preprocessing. Organize the family searching samples into the following format: y={str _j :(v _j1 /v _j2 )}, where str _j represents the name of the jth STR locus, and v _jk represents the STR at locus j on the kth chromosome eigenvalues of .

Step 2: Calculate the parent-child relationship index. For sample y, traverse str _j :(v _j1 /v _j2 ), if there is a domain d _m corresponding to str _j , then obtain the sample sets corresponding to the indices of v _j1 and v _j2 , denoted as X _j1 and X _j2 respectively. Take the union of X _j1 and X _j2 , denoted as After obtaining the X _j corresponding to each str _j , calculate the union of X _j Each element in X is a candidate sample. For each element x _i in X, compute in,

Then q _i is the parent-child relationship index of the candidate sample x _i .

Step 3: Determine whether there is a parent-child relationship. According to q _i , the candidate samples x _i are sorted in descending order. If q _i ≥ θ, it is considered that the donor of the sample y to be searched for relatives has a parent-child relationship with the donor of the candidate sample x _i ; otherwise, there is no parent-child relationship between the two . Among them, θ is the threshold value set in advance by the system, which can generally be considered to be set as the number of loci minus 1.

Specific examples are as follows:

The samples that need to be stored are shown in Table 1, and the samples to be found are shown in Table 2.

Table 1 Example of samples to be stored in the family tracing database

Sample ID 00001 00002 00003 00004 00005 ... D8S1179 14/15 13/15 10/13 13/15 13/14 ... D21S11 30.2/31 29/32.2 30/31.2 29/32.2 29/30 ... D7S820 10/11 8/9 11/11 11/11 10/12 ... CSF1PO 10/11 12/14 10/13 11/12 10/10 ... D3S1358 15/16 16/16 16/17 15/15 15/16 ... D5S818 10/11 11/12 11/13 10/11 10/13 ... D13S317 12/12 11/11 11/12 10/11 11/11 ... D16S539 10/13 9/11 11/12 11/12 10/12 ... D2S1338 20/23 21/23 18/24 20/23 18/19 ... D19S433 13/14 13/13 14/15 13/15.2 13/14 ... wxya 17/20 14/16 16/17 13/14 17/19 ... D12S391 18/21 19/20 17/17.3 18/19 18/18 ... D18S51 13/14 13/15 14/15 13/16 14/17 ... AMEL X/X X/Y X/Y X/Y X/Y ... D6S1043 14/21.3 19/20 13/14 10/19 17/18 ... FGA 19/22 19/24 23/24 24/26 23/23 ...

Table 2 Examples of Samples to be Searched for

site STR D8S1179 13/15 D21S11 29/31 D7S820 11/11 CSF1PO 11/11 D3S1358 15/15 D5S818 10/12 D13S317 10/10 D16S539 9/11 D2S1338 18/23 D19S433 13/14

wxya 14/14 D12S391 18/19 D18S51 13/15 AMEL X/Y D6S1043 10/18 FGA 23/24

1. STR data storage based on inverted index structure

Step 1: Data preprocessing. That is to organize all the samples to be stored into a standard format, taking sample No. 00001 as an example, the result after sorting is:

x ₁ ＝{D8S1179:(14/15),D21S11:(30.2/31),D7S820:(10/11),CSF1PO:(10/11),D3S1358:(15/16),D5S818:(10/11 ),D13S317:(12/12),D16S539:(10/13),D2S1338:(20/23),D19S433:(13/14),vWA:(17/20),D12S391:(18/21), D18S51:(13/14),AMEL:(X/X),D6S1043:(14/21.3),FGA:(19/22)}

Step 2: Create a data field. In this example, the locus names of all sample data are exactly the same, so there are 16 data domains created:

Step 3: Data storage. Data storage takes the sample whose ID is 00002 as an example. At this time, the sample whose ID is 00001 has been stored in the database, as shown in Figure 5. First, get the first set of data D8S1179: (13/15). At this time, there is a data field D8S1179 in the database, and there is index 15 but not index 13. Therefore, it is necessary to create a new index for 13, and add 00002 to 13 and 15 In the index, as shown in Figure 6, each data field of sample 00002 is traversed sequentially in the above manner.

2. Paternity identification sorting and comparison method based on inverted index structure

Step 1: Data preprocessing.

Organize the family search samples in Table 2 into the following format:

y＝{D8S1179:(13/15),D21S11:(29/31),D7S820:(11/11),CSF1PO:(11/11),D3S1358:(15/15),D5S818:(10/12) ,D13S317:(10/10),D16S539:(9/11),D2S1338:(18/23),D19S433:(13/14),vWA:(14/14),D12S391:(18/19),D18S51 :(13/15),AMEL:(X/Y),D6S1043:(10/18),FGA:(23/24)}

Step 2: Calculate the parent-child relationship index.

For the sample y, firstly, for the first data field D8S1179, which has indexes of 13 and 15, take the union of its sample sets X _j ={00001,00002,00003,00004,00005,...}, based on Compute the union of all domains X = {00001, 00002, 00003, 00004, 00005, . . . }. For each element x _i in X, calculate its score, as shown in Table 3:

Table 3 Sample Scores

Sample ID 00001 00002 00003 00004 00005 ... D8S1179 1 1 1 1 1 ... D21S11 0 1 0 1 1 ... D7S820 1 0 1 1 0 ... CSF1PO 1 0 0 1 0 ... D3S1358 1 0 0 1 1 ... D5S818 1 1 0 1 1 ... D13S317 0 0 0 1 0 ... D16S539 0 1 1 1 0 ... D2S1338 1 1 1 1 1 ... D19S433 1 1 1 1 1 ... wxya 0 1 0 1 0 ... D12S391 1 1 0 1 1 ... D18S51 1 1 1 1 0 ... AMEL 1 1 1 1 1 ... D6S1043 0 0 0 1 1 ... FGA 0 1 1 1 1 ... q _i 10 11 8 16 10

Step 3: Determine whether there is a parent-child relationship.

The candidate samples are sorted in descending order according to the scores, and if θ=15, it can be judged that sample 00004 has a parent-child relationship with y.

The prototype of the database system designed according to this system is shown in Figure 7 and Figure 8, where Figure 7 shows the STR data stored based on the inverted index structure described in this patent, and Figure 8 shows the result of family search.

To sum up, the present invention proposes an inverted index structure-based method for storing STR data and sorting and comparing paternity tests. The method stores the paired STR locus data in the form of an inverted index by establishing a data field and an index of STR data values; method, calculate the parent-child relationship index between samples, realize the rapid comparison of paternity identification, improve the efficiency of retrieval query, reduce the impact of gene mutation on the comparison efficiency of parent-child identification; and due to the use of data fields, greatly improve the scope of application of this method.

Claims (7)

1. The STR data storage and paternity test sequencing comparison method based on the inverted index structure is characterized by comprising the following steps of:

1) STR data storage based on inverted index structure

Firstly, preprocessing all STR data, and arranging an STR data set of each sample into a standard format; then, each locus is used as a data field, and each data field stores respective STR data; finally, storing the STR data in a reverse index mode;

2) paternity test ordering comparison based on STR data stored in inverted index mode

Firstly, preprocessing STR data to be searched, and sorting the STR data set of each sample into a standard format; then, comparing the STR data of each locus in respective data fields, and forming a final paternity index; and finally, judging whether the samples have the parent-child relationship, if the parent-child relationship index is higher than a specific value, considering that the donor of the candidate sample and the donor of the sample to be searched have the parent-child relationship, otherwise, considering that the parent-child relationship does not exist between the candidate sample and the candidate sample.

2. The method for storing STR data and comparing paternity test and rank order based on the inverted index structure of claim 1, wherein in step 1), the STR data is preprocessed, and the STR data set of each sample is arranged into a standard format, specifically as follows:

denote the sample data set as X ═ X₁,x₂,…,x_n}；

Wherein x is_iRepresents the STR data of the i-th individual,wherein,denotes the name of the jth STR locus, v_jkRepresents the characteristic value of STR at locus j on the kth chromosome.

3. The STR data storage and paternity test sequencing comparison method based on the inverted index structure of claim 2, wherein the data fields in step 1) are established as follows:

traversing STR data of all samples, and establishing a set STR of STR locus names_N＝{str₁,str₂,…,str_mFor STR_NEach str in (1)_iEstablishing different data fields, denoted as d_i；i＝1,2……m。

4. The method for STR data storage and paternity test ranking comparison based on inverted index structure of claim 2, wherein in step 1) STR data is stored in inverted index mode, sample data set X is traversed, and any X is compared_iGo throughIf it is notCorresponding data field d_mIn the presence of v_j1Index of (1), then x_iAdding to the index; if v is not present_j1The index is established, and x is added_iAdding into the index; for v_j2The treatment was carried out in the same manner.

5. The STR data storage and paternity test sorting comparison method according to claim 1, wherein the STR data to be searched for is preprocessed in step 2), specifically as follows:

the seeking parent sample is arranged into the following format: y ═ str_j:(v_j1/v_j2) In which str_jDenotes the name of the jth STR locus, v_jkRepresents the characteristic value of STR at locus j on the kth chromosome.

6. The method for STR data storage and paternity test sequencing comparison based on inverted index structure of claim 5, wherein the paternity index in step 2) is calculated as follows:

for sample y, go through str_j:(v_j1/v_j2) If str is present_jCorresponding field d_mThen obtain v_j1And v_j2The sample sets corresponding to the indexes are respectively marked as X_j1And X_j2；

Taking X_j1And X_j2Is a union of (1), denoted X_j＝X_j1∪X_j2；

After obtaining each str_jCorresponding X_jThen, X is calculated_jX ═ X₁∪X₂∪…∪X_JEach element in X is a candidate sample;

q is then_iIs a candidate sample x_iThe parentage relations index of (1).

7. The STR data storage and paternity test ranking comparison method according to claim 6, wherein in step 2), it is determined whether there is a paternity relationship, specifically as follows:

according to q_iFor candidate sample x_iSorting in descending order, if q_iIf the value is more than or equal to theta, the donor of the sample y to be searched and the candidate sample x are considered_iThe donor of (a) has a parent-child relationship; otherwise, the parent-child relationship does not exist between the two; where θ is a threshold value preset by the system, and is the number of loci minus 1.