(19)中华人民共和国国家知识产权局
(12)发明专利说明书 | ||
(10)申请公布号 CN 105260395 A (43)申请公布日 2016.01.20 | ||
(21)申请号 CN201510590067.X
(22)申请日 2015.09.16
(71)申请人 中国人民解放军第四军医大学
地址 710032 陕西省西安市长乐西路169号
(72)发明人 刘健 李宝娟 高东怀 许卫中 孙茂 许浩 靳豪杰 张军超
(74)专利代理机构 西安通大专利代理有限责任公司
代理人 徐文权
(51)Int.CI
G06F17/30
权利要求说明书 说明书 幅图 |
(54)发明名称
基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法 | |
(57)摘要
本发明公开了一种基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法，属于数据存储及处理技术领域。本发明基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法，主要包括两个方面：一是基于倒排索引结构的STR数据存储方法，该方法会依据样本所选取STR基因座，建立不同的数据域，在数据域中将STR数据以倒排索引结构存储；二是亲子鉴定排序比对方法，该方法基于划分域的倒排索引结构，计算寻亲样本与数据库中样本的亲缘关系，实现快速、稳定、可靠的在线寻亲。 | |
法律状态
法律状态公告日 | 法律状态信息 | 法律状态 |
权 利 要 求 说 明 书
1.基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法，其特征在于，包括以下步骤：
1)基于倒排索引结构的STR数据存储
首先，将所有STR数据进行预处理，将每个样本的STR数据集整理为标准格式；然后，将每一个位点作为一个数据域，每个数据域中将存储各自的STR数据；最后，将STR数据以倒排索引的方式存储；
2)基于以倒排索引的方式存储的STR数据的亲子鉴定排序比对
首先，将待寻亲STR数据进行预处理，将每个样本的STR数据集整理为标准格式；然后，将每个位点的STR数据在各自的数据域中进行比对，并形成最终的亲子关系指数；最后，判定样本之间是否存在亲子关系，如果亲子关系指数高于特定的值，则认为候选样本的供体与待寻亲样本的供体具有亲子关系，反之则认为两者之间不存在亲子关系。
2.根据权利要求1所述的基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法，其特征在于，步骤1)中，对STR数据进行预处理，将每个样本的STR数据集整理为标准格式，具体如下：
将样本数据集记为X＝{x<Sub>1</Sub>,x<Sub>2</Sub>,…,x<Sub>n</Sub>}；
其中，x<Sub>i</Sub>表示第i个个体的STR数据，<Image>其中，<Image>表示第j个STR基因座的名称，v<Sub>jk</Sub>表示第k个染体上基因座j上STR的特征值。
3.根据权利要求2所述的基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法，其特征在于，步骤1)中数据域的建立如下：
遍历所有样本的STR数据，建立STR基因座名称的集合STR<Sub>N</Sub>＝{str<Sub>1</S
ub>,str<Sub>2</Sub>,…,str<Sub>m</Sub>}，针对STR<Sub>N</Sub>中的每个str<Sub>i</Sub>，建立不同的数据域，记为d<Sub>i</Sub>；i＝1,2……m。
4.根据权利要求2所述的基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法，其特征在于，步骤1)中将STR数据以倒排索引的方式存储，遍历样本数据集X，对任意x<Sub>i</Sub>，遍历<Image>如果<Image>对应的数据域d<Sub>m</Sub>中存在v<Sub>j1</Sub>的索引，则将x<Sub>i</Sub>添加到该索引中；如果不存在v<Sub>j1</Sub>的倒排索引，则建立该索引，并将x<Sub>i</Sub>添加到索引中；对于v<Sub>j2</Sub>采用相同的方式进行处理。
5.根据权利要求1所述的基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法，步骤2)中将待寻亲STR数据进行预处理，具体如下：
将寻亲样本整理为如下格式：y＝{str<Sub>j</Sub>:(v<Sub>j1</Sub>/v<Sub>j2</Sub>)}，其中str<Sub>j</Sub>表示第j个STR基因座的名称，v<Sub>jk</Sub>表示第k个染体上基因座j上STR的特征值。
6.根据权利要求5所述的基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法，步骤2)中亲子关系指数的计算如下：
对于样本y，遍历str<Sub>j</Sub>:(v<Sub>j1</Sub>/v<Sub>j2</Sub>)，如果存在str<Sub>j</Sub>对应的域d<Sub>m</Sub>，则获得v<Sub>j1</Sub>和v<Sub>j2</Sub>索引所对应的样本集合，分别记为X<Sub>j1</Sub>和X<Sub>j2</Sub>；
取X<Sub>j1</Sub>和X<Sub>j2</Sub>的并集，记为X<Sub>j</Sub>＝X<Sub>j1</Sub>∪X<Sub>j2</Sub>；
在获得每个str<Sub>j</Sub>所对应的X<Sub>j</Sub>后，计算X<Sub>j</Sub>的并集X＝X<Sub>1</Sub>∪X<Sub>2</Sub>∪…∪X<Sub>J</Sub>，X中的每个元素均为候选样本；
</Image>
则q<Sub>i</Sub>为候选样本x<Sub>i</Sub>的亲子关系指数。
7.根据权利要求6所述的基于倒排索引结构的STR数据存储及亲子鉴定排序比对方法，步骤2)中判断是否存在亲子关系，具体如下：
依据q<Sub>i</Sub>对候选样本x<Sub>i</Sub>进行降序排序，如果q<Sub>i</Sub>≥θ，则认为待寻亲样本y的供体与候选样本x<Sub>i</Sub>的供体具有亲子关系；反之，则认为两者之间不存在亲子关系；其中，θ为系统事先设定的阈值，为基因座的数量减1。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论