个体单体型问题参数化算法研究

个体单体型问题指如何利用个体DNA测序片断数据,根据不同的优化准则确定该个体单体型的计算问题.因为技术上的限制,DNA测序实验中能直接测定的片断长度是有限的,一个片断所覆盖的最大SNP位点数k1通常小于10;出于时间和金钱的考虑,覆盖一个SNP位点的最大片断数k2也不是很大,通常约为10左右;与要测定的单体型SNP位点总数n及所测序的DNA片断总数m相比,k1和k2均很小.在此基础上,文中对个体单体型问题最少SNP位点删除MSR和最少片段删除MFR模型进行了参数化,提出了时间复杂度分别为O(nk1k2+mlogm+mk1)和O(mk22+mk1k2+mlogm+nk2)求解无空隙MSR和MFR的精确算法.和Bafna等提出的时间复杂度为O(mn2)和O(m2n+m3)的精确算法相比,文中的算法效率提高了很多,具有较高的实用价值.

数据仓库的多维数据模型的研究

多维数据模型是数据仓库和联机分析处理研究中的一个重要问题,该文根据电力负荷数据集的特点,提出了一种新模型,解决不同维公用一个底层层次属性,把系统中不完全的低粒度数据集和完全的粗粒度数据集在逻辑上无缝地结合起来支持联机分析处理的问题,这是其他多维数据模型所没有解决的。

有Mate-Pairs的个体单体型MSR问题的参数化算法

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2~kn^2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k_1-1)k_22^(2h)+(k_1+1)^(2h)+nk_2+mk_1)的新算法,其中,k_1为一个片断覆盖的最大SNP位点数(不大于n),k_2为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k_2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.

单体型组装最大片段割参数化精确算法

单体型能提高复杂疾病全基因组关联分析的能力,可直接用生物实验测定单体型费用太高.随着DNA测序技术的发展,计算机算法被广泛用于从个体基因组测序片段上构建单体型,即单体型组装.最大片段割是最近提出的一个单体型组装优化模型,是NP-难的,目前没有实用精确算法.最近参数计算理论利用实际计算中的小参数特征为NP-难问题求解提供了一条新思路.本文根据实际测序数据覆盖了两个或多个杂合单核苷酸多态性位点(SNP)的片段的测序深度较小的特点,对跨一个具体SNP位点的所有片段划分进行枚举,提出一个参数化的动态规划算法求解其精确解.大量测试结果表明该算法比已有的启发式算法有更高的单体型重建精度.

单体型组装MEC问题的参数化算法研究

单体型组装MEC问题指如何利用个体的DNA测序片断数据,翻转最少的SNP位点值以确定该个体单体型的计算问题。根据片段数据的特点提出了一个时间复杂度为O(nk22k2+mlogm+mk1)的参数化算法,其中m为片段数,n为单体型的SNP位点数,k1为一个片断覆盖的最大SNP位点数(通常小于10),k2为覆盖同一SNP位点的片段的最大数(通常不大于10)。对于实际DNA测序中的片段数据,即使m和n都相当大,该算法也可以在较短的时间得到MEC问题的精确解,具有良好的可扩展性和较高的实用价值。

复杂疾病模型快速参数求解算法

全基因组关联研究(GWAS)是在探究人类复杂疾病相关基因的重要方法,实用有效的算法是GWAS成功的关键,因此根据疾病模型生成模拟数据对GWAS算法进行比较测试具有重要的意义。模拟测试要求根据各种输入的控制量计算出疾病模型的相关参数,但是目前缺乏相关公开的算法。提出了一个求解这些参数的分支限界算法。大量实验测试表明该算法能快速精确地计算出疾病模型的相关参数,可用于搭建GWAS算法测试平台。

分布式数据源的实视图维护算法研究

数据仓库作为决策支持系统的集成化数据中心,其数据可以认为是定义在多个不同数据源的实视图集。近年来数据仓库中实视图维护算法的研究激起很多学者的重视。当多个独立的数据源出现并发更新时传统的实视图维护算法可能导致视图维护异常,本文提出了一个双向扫描并行处理实视图维护(BSP)算法,能确保实视图与数据源的完全一致性,并通过实验与其它类似的算法进行了比较,说明本算法具有较高的效率。

谈计算机专业学生的数学基础

计算机技术本质上是一种数学技术,我国计算机专业学生的数学基础相对薄弱,夯实数学基础、提高数学能力是培养计算机专业高素质研究型人才的有效途径。

两位点疾病模型的快速参数求解算法

生成模拟数据对全基因组关联分析(GWAS)算法进行测试时,要求按单位点边缘效应大小计算出疾病模型的相关参数,而目前缺乏对应的公开算法。为此,基于二分搜索提出一个数值算法,根据单位点边缘效应和人群疾病发病率计算出3个典型的两位点疾病模型的控制参数。实验结果表明,该算法能快速精确地进行疾病模型参数求解,便于对GWAS算法进行大规模模拟测试。

单体型组装问题MEC／GI模型的参数化算法

根据 DNA 测序片段数据的特点,提出了一个时间复杂度为 O(nk_22^(k_2)+mlogm+mk_1)的单体型组装问题 MEC/GI 模型的参数化算法,其中 m 为片段数,n 为单体型的 SNP位点数,k_1 为一个片段覆盖的最大 SNP 位点数(通常小于10),k_2为覆盖同一 SNP 位点的片段的最大数(通常不大于10)。对于实际 DNA 测序中的片段数据,即使 m 和 n 都相当大,该算法也可以在较短的时间得到 MEC/GI 模型的精确解,具有良好的可扩展性和较高的实用价值。

枚举单体型组装问题多个最优解的遗传算法设计

单体型组装问题就是根据个体基因组测序获得的DNA序列数据重构出该个体的一对单体型。目前单体型组装问题的各种优化计算模型已有相关的启发式算法和参数化精确算法,但是这些算法只能得出一个最优解,即一对单体型。可是生物问题的最优解往往不是唯一的,或者真实解可能只是接近最优的。该文设计了一个新的能枚举出最优的多个解的遗传算法。实验结果表明该算法具有较高的单体型重建精度,并为生物学家根据领域知识在算法获得的多个解的基础进一步选择提供了可能。

数据库技术在生物信息学中的应用

阐述了生物信息学研究中重要的数据库及其应用,并对其发展进行了展望.

从数学看计算机学科研究型人才的培养

数学是计算机科学的核心和灵魂,数学水平的高低直接影响到计算机学科本科及其以上层次人才的创新和研究能力。我国计算机学科发展需要培养研究型人才,夯实高等数学基础知识、提高数学运用能力、增强应用数学的意识,是培养计算机专业研究型人才的有效途径。

N阶魔方阵的算法

本文首先介绍了魔方阵的概念及其奇数阶的解法 ,进而提出了偶数阶魔方阵的一种算法 ,并给出了

WDM光纤网故障的光路恢复策略

鉴于近年来波分复用(WDM)系统在长途光纤主干网上得到了愈来愈广泛的应用这一情况,针对如何确保网络的故障恢复(restoration)能力,尽可能缩短故障恢复时间,减少故障恢复代价等问题;概述了一些恢复策略,讨论了它们的性能并对其前景进行展望。

机器学习方法在基因交互作用探测中的研究进展

复杂疾病是基因与基因、基因与环境交互作用的结果,高维基因交互作用的探测给计算带来了极大的挑战。在过去20年间,机器学习方法被用于探测基因-基因交互作用,并取得了一定的效果。本文综述了机器学习方法在基因交互作用探测中的研究进展,系统地介绍了神经网络(neural networks,NN)、随机森林(random forest,RF)、支持向量机(support vector machines,SVM)和多因子降维法(multifactor dimensionality reduction,MDR)等机器学习方法在全基因组关联研究(genome wide association study,GWAS)中探测基因交互作用的原理和局限性,并对未来的研究进行了展望。

单体型组装问题计算模型的比较与分析

单体型检测在遗传病基因的定位、药理反应的研究、个体识别等方面有极其广阔的应用前景。单体型组装问题指如何利用个体的基因测序片断数据,根据不同的优化准则确定该个体单体型的计算问题。对MSR,MFR,MEC,WMLF,MEC/GI等单体型组装模型做了详细的分析比较,得出了如下结论:在没有引入测序误差情况下,上述模型的重构精度基本一致。随着测序误差的增加,MEC/GI模型的容错性最好,重构精度最高;MSR模型受测序误差的影响最大,只适用于测序误差极小的情形。

一种基于Stirling图枚举算法的分球入盒问题求解

已有的分球入盒问题解法通常只关注分球的总方案数,目前尚没有公开的计算机算法来枚举出所有具体的分球方案,而方案的枚举是生物信息学中一些分区优化算法的基础。受第二类Stirling数的递推公式的启发,提出一个新的数据结构——Stirling图。在此基础上设计一个算法来枚举p个不同球分配到q个相同盒子里的所有不同的方案。当p和q较大,枚举出所有的方案不可行时,设计另一个算法在整个方案空间实现均匀采样,输出指定个数的方案。测试结果表明,这些算法在内存为8 GB的普通PC上可在合理的时间内枚举出上百万组不同的方案。