数学建模有关DNA序列k-mer index的问题

article/2025/3/15 17:03:46

原问题是这样的:

给定一个DNA序列,这个系列只含有4个字母ATCG,如 S =“CTGTACTGTAT”。给定一个整数值k,从S的第一个位置开始,取一连续k个字母的短串,称之为k-mer(如k= 5,则此短串为CTGTA), 然后从S的第二个位置, 取另一k-mer(如k= 5,则此短串为TGTAC),这样直至S的末端,就得一个集合,包含全部k-mer 。 如对序列S来说,所有5-mer为{CTGTA,TGTAC,GTACT,TACTG,ACTGT,TGTAT}。

通常这些k-mer需一种数据索引方法,可被后面的操作快速访问。例如,对5-mer来说,当查询CTGTA,通过这种数据索引方法,可返回其在DNA序列S中的位置为{1,6}。

现在以文件形式给定 100万个 DNA序列,序列编号为1-1000000,每个基因序列长度为100 。

(1)要求对给定k, 给出并实现一种数据索引方法,可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引,只需支持一个k值即可,不需要支持全部k值。

(2)要求索引一旦建立,查询速度尽量快,所用内存尽量小。

(3)给出建立索引所用的计算复杂度,和空间复杂度分析。

(4)给出使用索引查询的计算复杂度,和空间复杂度分析。

(5)假设内存限制为8G,分析所设计索引方法所能支持的最大k值和相应数据查询效率。

(6)按重要性由高到低排列,将依据以下几点,来评价索引方法性能 

l 索引查询速度

l 索引内存使用

l 8G内存下,所能支持的k值范围

l 建立索引时间

本题主要是有关DNA序列的k-mer index查找问题,可将其转化为字符串的查找匹配模型问题,在处理字符串查找问题上,现在得到广泛认可的算法有适合处理字符串单模匹配的KMP算法,BM算法,以及适合处理字符串多模匹配的AC算法,WM算法等等。我们队以hash算法为基础,并作了几点优化和改进,使算法的内存占用有了一定程度的降低,查找效率也有很大提高。

本文中的算法和其它大多数算法一样,在建立索引时采用了hash算法,不同的是,我们利用一个hash函数(将DNA序列中的ATCG分别用二进制位的00,01,10,11来表示),这样做不但把DNA序列映射为一个整数,便于存储与查找,而且可以减少内存的使用,在k值取值较大时减耗尤其明显。在解决hash函数的地址冲突时,我们采用了拉链法,并且采用多级链表的形式,这样在确保查询效率较高的情况下,同样也可以减少内存的使用。

由于我们将DNA序列的ATCG分别表示为00,01,10,11,则我们可以将任意一个k-mer串映射为一个十进制整数。

假如我们的k-mer串长度为5,DNA序列ATCGA,则出于二进制左高位右低位的表示习惯考虑,我们也按照从左到右的顺序表示。则转化后如图所示。


在使用hash算法时,我们不可避免会遇到地址冲突的情况,在该算法中我们采用拉链法解决地址冲突。

 

我们首先以hash 表的数组元素为链表的头结点,然后采用直接插入法插入到有序链表中,假如已经存在一个key值为781的结点,如图所示。



为了进一步提高查找效率,我们将key值相同的元素采用头插法插入到一个新的链表中。

假如我们又插入一个key值为228的结点,如图。


好了,废话少说了,现将源码附录如下:

#include <stdio.h>

#include <malloc.h>

#include <math.h>

#include <process.h>

#include <time.h>

#define M 14557

typedef struct seq

{

int value;

int num;

char index;

struct seq *next1;

struct seq *next2;

}*Seq,Sequence;

void initNode(Seq *r,int i)

{

if(*r==NULL)

{

*r=(Seq)malloc(sizeof(Sequence));

(*r)->next1=NULL;

(*r)->next2=NULL;

}

}

void addNode(Seq *r,int v,int n,int i)

{

Seq s=(*r)->next1;

Seq p=*r;

if(s)

{

while(s&&v>s->value)

{

p=s;

s=s->next1;

}

if(s&&v==s->value)

{

Seq qsub=(Seq)malloc(sizeof(Sequence));

qsub->value=v;

qsub->index=(char)i;

qsub->num=n;

qsub->next1=NULL;

qsub->next2=s->next2;

s->next2=qsub;

}

else

{

Seq q=(Seq)malloc(sizeof(Sequence));

q->next1=s;

q->value=v;

q->index=(char)i;

q->num=n;

q->next2=NULL;

p->next1=q;

}

}

else

{

Seq q=(Seq)malloc(sizeof(Sequence));

q->next1=s;

q->value=v;

q->index=(char)i;

q->num=n;

q->next2=NULL;

(*r)->next1=q;

}

}

void consultNode(Seq s,int v,int *count)

{

Seq r;

if(s)

r=s->next1;

while(r&&v>=r->value)

{

if(v==r->value)

{

(*count)++;

printf("%d,%d\n",r->num,r->index);

Seq q=r->next2;

while(q)

{

(*count)++;

printf("%d,%d\n",q->num,q->index);

q=q->next2;

}

}

r=r->next1;

}

 

}

int main(){

int k,j,i;

int num,n;

int m=0;

int pos=1;

char s[200];

Seq seqarray[M]={NULL};

printf("请输入k值:\n");

scanf("%d",&k);

FILE *fp;

if((fp=fopen("h.fa","r"))==NULL)

{

printf("File open error!\n");

exit(1);

}

long int start=clock();

while(!feof(fp))

{

fscanf(fp,"%*s%s%d%d",s,&num,&j);

fgetc(fp);

fgetc(fp);

j=0;

m=0;

pos=1;

for(i=0;i<k;i++) //A:00 T:01 C:10 G:11

{

//建立索引的时间与k值有关,当k值较大时,当hash选择的p值为合适的质数时,建立索引的时间明显缩短

switch(fgetc(fp))

{

case 'A':

j+=2;

break;

case 'T':

m+=(int)pow(2,j);

j+=2;

break;

case 'C':

j++;

m+=(int)pow(2,j);

j++;

break;

case 'G':

m+=(int)pow(2,j);

j++;

m+=(int)pow(2,j);

j++;

break;

default:

break;

}

}

n=m%M;

initNode(&seqarray[n],n);

addNode(&seqarray[n],m,num,pos);

pos++;

while(pos<=100-k)

{

j-=2;

m>>=2;

switch(fgetc(fp))

{

case 'A':

j+=2;

break;

case 'T':

m+=(int)pow(2,j);

j+=2;

break;

case 'C':

j++;

m+=(int)pow(2,j);

j++;

break;

case 'G':

m+=(int)pow(2,j);

j++;

m+=(int)pow(2,j);

j++;

break;

default:

break;

}

n=m%M;

initNode(&seqarray[n],n);

addNode(&seqarray[n],m,num,pos);

pos++;

}

fgets(s,50,fp);

}

/

getchar();

long int end=clock();

printf("*************建立索引%ldms*************\n",end-start); //计算建立索引时间

printf("请输入要查询的K\n");

gets(s);

m=0;

j=0;

for(i=0;i<k;i++)

switch(s[i])

{

case 'A':

j+=2;

break;

case 'T':

m+=(int)pow(2,j);

j+=2;

break;

case 'C':

j++;

m+=(int)pow(2,j);

j++;

break;

case 'G':

m+=(int)pow(2,j);

j++;

m+=(int)pow(2,j);

j++;

break;

default:

break;

}

n=m%M;

int count=0;

long int start1=clock();

consultNode(seqarray[n],m,&count);

printf("*****查询到记录%d*****\n",count);

long int end1=clock();

printf("*************查询时间%ldms*************\n",end1-start1); //计算查询时间

fclose(fp);

/

for(j=0;j<M;j++) //释放内存从前往后

if(seqarray[j])

{

Seq p=seqarray[j]->next1;

Seq q;

Seq q1,q2;

while(p)

{

q=p->next1;

q1=p->next2;

while(q1)

{

q2=q1->next2;

free(q1);

q1=q2;

}

free(p);

p=q;

}

free(seqarray[j]);

 

}

return 0;

}





http://chatgpt.dhexx.cn/article/kOar70BT.shtml

相关文章

数学建模暑期集训26:遗传算法

遗传算法是优化类问题的经典智能算法。本篇将介绍遗传算法的基本概念以及利用遗传算法来求解单目标规划模型。 达尔文进化论的基本思想 遗传算法的设计是受到达尔文进化论的启发。先看下面这张图的几个基本概念。 一些花构成一个种群。 每朵花被称为个体。 每个个体内有染色…

2021年亚太杯三等奖选手C题思路

文章目录 亚太杯C题第一小问亚太杯C题第二小问亚太杯C题第三小问亚太杯C题第四小问亚太杯C题第五小问 昨天晚上刚出了亚太杯的成绩&#xff0c;获得了三等奖&#xff0c;毕竟是第一次参加数学建模比赛&#xff0c;不是成功参与奖就很高兴了&#xff0c;结束了之后&#xff0c;还…

python使用networks读取txt文件画一个有权有向图

class demo():def __init__(self):self.file_pathtest.txt#图文件 def draw_graph(self):G2 nx.DiGraph() # 创建&#xff1a;空的 有向图f open(self.file_path)lines [l.split() for l in f.readlines() if l.strip()]# print(lines)for i in lines:G2.add_edge(i[0],…

数学建模常用功能

目录 pandas读取数据 查看数据异常 提取指定列 将dataframe数据以numpy形式提取 数据划分 随机森林回归 GBDT回归 特征重要性可视化 输出&#xff1a; ​ 绘制3D散点图 导入自定义包且.py文件修改时jupyter notebook自动同步 dataframe删除某列中重复字段并删除对应行…

c语言文件操作

文件操作读写 1 文件处理原理及基本概念 C语言的文件处理功能&#xff0c;大体上分为两种&#xff1a;一种是设置缓冲区&#xff0c;另一种是不设置缓冲区。因为不设置缓冲区的方法直接对磁盘进行操作&#xff0c;速度较慢&#xff0c;并且由于不是C的标准函数&#xff0c;跨…

无人机视角展示(无人机图像定位 )--某数学建模A题MATLAB代码

近期没啥空&#xff0c;水个简单的。。。。 目前只写了第一问&#xff0c;有空再写。。。。。 问题描述 无人驾驶飞机简称“无人机”&#xff0c;是利用无线电遥控设备和自备的程序控制装置操纵的不载人飞机。搭载图像设备的无人机在高空航拍、区域巡视、军事侦查等方面有广泛…

2020 全国大学生数学建模竞赛C题思路+代码

题目链接&#xff1a;天翼云盘 珍藏美好生活 家庭云|网盘|文件备份|资源分享 前言 又是一年数据挖掘题型&#xff0c;第一次接触这种题型还是在去年的mathorcup上&#xff0c;这种题的难度就在于指标的建立和数据的处理上。后面会出一份关于数据挖掘题型&#xff0c;我的相关经…

PU learning半监督学习

半监督学习 Positive-unlabeled learning 什么是半监督学习 让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能&#xff0c;就是半监督学习&#xff08;semi-supervised learning&#xff09;。 要利用未标记样本&#xff0c;必然要做一些将未标记样本所揭示的数…

详解基于图卷积的半监督学习

Kipf和Welling最近发表的一篇论文提出&#xff0c;使用谱传播规则&#xff08;spectral propagation&#xff09;快速近似spectral Graph Convolution。 和之前讨论的求和规则和平均规则相比&#xff0c;谱传播规则的不同之处在于聚合函数。它使用提升到负幂的度矩阵D对聚合进行…

【半监督医学图像分割 2023】RCPS

文章目录 【半监督医学图像分割 2023 】RCPS摘要1. 介绍2. 相关工作2.1 医学图像分割2.1 半监督学习2.3 对比学习 3. 方法3.1 整体概述3.2 纠正伪监督3.3 双向Voxel对比学习。 4. 实验 【半监督医学图像分割 2023 】RCPS 论文题目&#xff1a;RCPS: Rectified Contrastive Pseu…

半监督之数据增强

目录 前言 传统常见的 Free Lunch for Few-shot Learning: Distribution Calibration Learning to Augment for Data-Scarce Domain BERT Knowledge Distillation MixText: Linguistically-Informed Interpolation of Hidden Space for Semi-Supervised Text Classificati…

半监督的语义分割

现阶段传统的语义分割已经逐渐走向瓶颈&#xff0c;你设计一个网络&#xff0c;修改一下U-Net增加一个模块&#xff0c;现在已经很难再出优秀的成果&#xff0c;大家对你的创新程度认可度也越来越低。所以现在大家在进行语义分割的时候往往需要自行创造出一些需求&#xff0c;比…

半监督学习介绍

转载地址 https://blog.csdn.net/ice110956/article/details/13775071 什么是半监督学习? 传统的机器学习技术分为两类&#xff0c;一类是无监督学习&#xff0c;一类是监督学习。 无监督学习只利用未标记的样本集&#xff0c;而监督学习则只利用标记的样本集进行学习。 但…

半监督目标检测相关方法总结

戳我&#xff0c;查看GAN的系列专辑~&#xff01; 等你着陆&#xff01;【GAN生成对抗网络】知识星球&#xff01; 作者丨kinredon知乎 编辑丨极市平台 来源丨https://zhuanlan.zhihu.com/p/404160115 近期阅读了一些半监督目标检测&#xff08;Semi-Supervised Object Detecti…

半监督深度学习

个人博客&#xff1a;wyxogo.top 半监督学习 在有标签数据无标签数据混合成的训练数据中使用的机器学习算法。一般假设&#xff0c;无标签数据比有标签数据多&#xff0c;甚至多得多。 要求&#xff1a; 无标签数据一般是有标签数据中的某一个类别的&#xff08;不要不属于的…

半监督学习深度学习算法

该文章主体摘自知乎糯米稻谷的文章&#xff0c;对一些细节添加了自己的理解 文章链接https 半监督学习 啥是半监督学习&#xff08;Semi-supervised Learning&#xff09;1.简单自训练&#xff08;simple self-training&#xff09;2.协同训练&#xff08;co-training&#xff…

深度半监督学习方法总结

深度神经网络已被证明在对大量标记数据进行监督学习的训练中是非常有效的。 但是大多数现实世界的数据并没有被标记&#xff0c;并且进行全部标记也是不太现实的&#xff08;需要大量的资源、时间和精力&#xff09;。 为了解决这个问题半监督学习 ( semi-supervised learning)…

深度半监督学习

半监督学习介绍 Zhu X, Goldberg A B. Introduction to semi-supervised learning[J]. Synthesis lectures on artificial intelligence and machine learning, 2009, 3(1): 1-130. 链接半监督 无监督学习&#xff1a;主要目的是从独立同分布采样中得到的n个独立样本中找到in…

半监督SVM

半监督SVM 什么是半监督学习半监督SVM要做什么TSVM 这里是阅读周志华的《机器学习》中关于半监督SVM&#xff08;S3VM&#xff09;的笔记。 什么是半监督学习 在数据的搜集中&#xff0c;获得标记数据的成本是高昂的&#xff0c;而获得未标记的数据则是低廉的&#xff0c;为此…

半监督学习代码实战

sklearn官方例子——用半监督学习做数字识别 什么是半监督学习 半监督学习很重要&#xff0c;为什么呢&#xff1f;因为人工标注数据成本太高&#xff0c;现在大家参加比赛的数据都是标注好的了&#xff0c;那么如果老板给你一份没有标注的数据&#xff0c;而且有几百万条&am…