全基因组结构分析的组合问题与算法

结题报告
项目介绍
AI项目解读

基本信息

  • 批准号：
    61872427
  • 项目类别：
    面上项目
  • 资助金额：
    63.0万
  • 负责人：
    姜海涛
  • 依托单位：
    山东大学
  • 学科分类：
    F0201.计算机科学的基础理论
  • 结题年份：
    2022
  • 批准年份：
    2018
  • 项目状态：
    已结题
  • 起止时间：
    2019-01-01 至2022-12-31

项目摘要

Designing algorithms for combinatorial optimization problems in whole genome structure analysis is an important subject in theoretical computer science. Both genome maximal strip problem and double cut and join rearrangement problem are typical problems in whole genome structure analysis. This project is aiming at: designing new polynomial time approximation algorithms for the maximal strip problem and its complementary problem on genomes without repetition by non-oblivious local search methods, and the approximation factors reach to 3 and 2 respectively; designing a new polynomial time approximation algorithm for the maximal strip problem on genomes with repetitions by linear programming and rounding methods, and the approximation factor reaches to 16/7; designing a new polynomial time 1.375-approximation algorithm and a fixed-parameter time 4/3-approximation algorithm for double cut and join rearrangement problem on unsigned genomes without repetition; designing the first polynomial time approximation algorithm for the problem of breakpoint elimination by double cut and join on genomes with repetitions, with an approximation factor of 1.5. In this project, pursuing better approximation factor is the basic task for designing approximation algorithms. New algorithms of better performance on genome structure analysis problems can have guiding effect on the detection and prediction of genetic diseases.
设计全基因组结构分析中组合问题的算法是理论计算机领域的重要研究内容。基因组最长公共序列问题和二次切割并连接问题都是全基因组结构分析中的典型组合问题。本项目旨在，采用非直接局部搜索技术，设计无重复基因组的最长公共序列原问题和补问题的新多项式时间近似算法，近似性能比分别达到2和3；采用线性规划随机取整技术，设计有重复基因组的最长公共序列问题的新多项式时间近似算法，近似性能比达到16/7；设计无重复无向基因组二次切割并连接问题的近似性能比达到1.375的新多项式时间近似算法，以及近似性能比达到4/3的参数时间近似算法；设计有重复基因组的二次切割并连接断点消除问题的第一个近似算法，近似性能比达到1.5。本项目以竞逐更好的近似性能比作为设计近似算法的根本目标。全基因组结构分析问题的更好性能的新算法，对于遗传疾病的检测和预测具有指导意义。

结项摘要

基因组分析和比较是计算基因组学研究的重要内容之一，对于疾病的检测和预测、探索物种的进化规律有着重要的意义。用计算的方法分析基因组面临的最大挑战是基因组的重复性、不确定性、不完整和存在噪声。为克服这些困难，本项目研究了基因组最长公共序列问题、基因组片段填充问题以及多种模型下的基因组重排问题等典型的组合优化问题。旨在分析证明问题的计算复杂度，设计精确算法或近似算法。主要成果如下：.（1）当基因组都用PQ-树表示时，证明了其断点距离问题和断点中心问题都是NP-难的，并设计了断点距离问题的第一个参数算法。.（2）采用非直接局部搜索技术，设计无重复基因组的最长公共序列补问题的近似性能比为2的多项式时间近似算法。采用线性规划非线性取整技术，设计有重复基因组的最长保守序列问题的近似比为32(k-1)3e3/8e(k-1)-1的近似算法，不证明该问题为APX-hard。.（3）以最大保守对数为优化目标，证明片段填充问题是NP-难的，并设计了近似比为12/7近似算法。以最大公共邻接数为优化目标，设计了近似比为1.4+的近似算法。.（4）对于DCJ模型下的重排问题，设计了有重复序列的近似比为1.44的多项式算法和无重复序列的近似比为4/3的参数时间近似算法。对于移位、有限块移动模型下的重排问题，分别设计了近似比为1.375和3c/5的多项式时间近似算法，其中c表示最大移动距离。.这些问题模型能有效的刻画基因组比较和分析的目标，所设计的算法能有效揭示基因组的潜在性质。.

项目成果

期刊论文数量（7）
专著数量（0）
科研奖励数量（0）
会议论文数量（2）
专利数量（0）
Algorithms and Hardness for Scaffold Filling to Maximize Increased Duo-preservations
支架填充的算法和硬度，以最大限度地增加双体保存
  • DOI：
    10.1109/tcbb.2021.3083896
  • 发表时间：
    2021
  • 期刊：
    IEEE/ACM Transactions on Computational Biology and Bioinformatics
  • 影响因子：
    --
  • 作者：
    Jingjing Ma;Haitao Jiang;Daming Zhu;Runmin Yang
  • 通讯作者：
    Runmin Yang
Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
有界度图上最大顶点覆盖问题的近似算法
  • DOI：
    10.1016/j.tcs.2021.07.015
  • 发表时间：
    2021
  • 期刊：
    THEORETICAL COMPUTER SCIENCE
  • 影响因子：
    --
  • 作者：
    Zhou Peiyan;Jiang Haitao;Zhu Daming;Zhu Binhai
  • 通讯作者：
    Zhu Binhai
Approximation algorithms for sorting by bounded singleton moves
通过有界单例移动排序的近似算法
  • DOI：
    10.1016/j.tcs.2022.03.011
  • 发表时间：
    2022
  • 期刊：
    Theoretical Computer Science
  • 影响因子：
    1.1
  • 作者：
    Shengjun Xie;Haodi Feng;Haitao Jiang;Daming Zhu
  • 通讯作者：
    Daming Zhu
Maximum Stacking Base Pairs: Hardness and Approximation by Nonlinear Linear Programming-Rounding
最大堆叠碱基对：非线性线性规划舍入的硬度和近似
  • DOI：
    10.1089/cmb.2019.0288
  • 发表时间：
    2020
  • 期刊：
    Journal of Computational Biology
  • 影响因子：
    1.7
  • 作者：
    Lixin Liu;Haitao Jiang;Peiqiang Liu;Binhai Zhu;Daming Zhu
  • 通讯作者：
    Daming Zhu
On the solution bound of two-sided scaffold filling
两侧支架填充的解界
  • DOI：
    10.1016/j.tcs.2021.04.024
  • 发表时间：
    2021
  • 期刊：
    THEORETICAL COMPUTER SCIENCE
  • 影响因子：
    --
  • 作者：
    Ma Jingjing;Zhu Daming;Jiang Haitao;Zhu Binhai
  • 通讯作者：
    Zhu Binhai

数据更新时间：{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI：
    {{ item.doi || "--"}}
  • 发表时间：
    {{ item.publish_year || "--" }}
  • 期刊：
    {{ item.journal_name }}
  • 影响因子：
    {{ item.factor || "--"}}
  • 作者：
    {{ item.authors }}
  • 通讯作者：
    {{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ monograph.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ patent.updateTime }}

其他文献

短块移动排序的14/11近似算法
  • DOI：
    --
  • 发表时间：
    --
  • 期刊：
    中国科学E辑
  • 影响因子：
    --
  • 作者：
    姜海涛;朱大铭
  • 通讯作者：
    朱大铭
非酒精肝中枯否细胞的表型变化
  • DOI：
    --
  • 发表时间：
    2016
  • 期刊：
    INTERNATIONAL JOURNAL OF CLINICAL AND EXPERIMENTAL MEDICINE
  • 影响因子：
    --
  • 作者：
    李阳;姜海涛
  • 通讯作者：
    姜海涛
SHPB加载下含不同倾角裂隙的类岩石试样力学特性
  • DOI：
    --
  • 发表时间：
    2016
  • 期刊：
    科技导报
  • 影响因子：
    --
  • 作者：
    王卫华;李坤;王小金;姜海涛;严哲
  • 通讯作者：
    严哲
An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies.
一种改进的脚手架填充近似算法，可最大化常见邻接。
  • DOI：
    --
  • 发表时间：
    --
  • 期刊：
    IEEE/ACM Transactions on Computational Biology and Bioinformatics
  • 影响因子：
    --
  • 作者：
    柳楠;姜海涛;朱滨海;朱大铭
  • 通讯作者：
    朱大铭
PQ-树断点距离中心问题的复杂性和精确算法
  • DOI：
    --
  • 发表时间：
    2016
  • 期刊：
    计算机研究与发展
  • 影响因子：
    --
  • 作者：
    刘培霞;姜海涛;朱大铭
  • 通讯作者：
    朱大铭

其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI：
    {{ item.doi || "--" }}
  • 发表时间：
    {{ item.publish_year || "--"}}
  • 期刊：
    {{ item.journal_name }}
  • 影响因子：
    {{ item.factor || "--" }}
  • 作者：
    {{ item.authors }}
  • 通讯作者：
    {{ item.author }}
empty
内容获取失败，请点击重试
重试联系客服
title开始分析
查看分析示例
此项目为已结题，我已根据课题信息分析并撰写以下内容，帮您拓宽课题思路：

AI项目思路

AI技术路线图

姜海涛的其他基金

对称翻转和转位问题的计算复杂性与算法
  • 批准号：
  • 批准年份：
    2022
  • 资助金额：
    53 万元
  • 项目类别：
    面上项目
基因组比较中三个组合问题的算法研究
  • 批准号：
    61202014
  • 批准年份：
    2012
  • 资助金额：
    24.0 万元
  • 项目类别：
    青年科学基金项目

相似国自然基金

{{ item.name }}
  • 批准号：
    {{ item.ratify_no }}
  • 批准年份：
    {{ item.approval_year }}
  • 资助金额：
    {{ item.support_num }}
  • 项目类别：
    {{ item.project_type }}

相似海外基金

{{ item.name }}
{{ item.translate_name }}
  • 批准号：
    {{ item.ratify_no }}
  • 财政年份：
    {{ item.approval_year }}
  • 资助金额：
    {{ item.support_num }}
  • 项目类别：
    {{ item.project_type }}
{{ showInfoDetail.title }}

作者：{{ showInfoDetail.author }}

知道了

AI项目解读示例

课题项目：调控A型流感病毒诱导IFN-β表达的机制研究

AI项目摘要：

本研究聚焦于TRIM2蛋白在A型流感病毒诱导的IFN-β表达中的调控机制。A型流感病毒是全球性健康问题，其感染可导致严重的呼吸道疾病。IFN-β作为关键的抗病毒因子，其表达水平对抗病毒防御至关重要。然而，TRIM2如何调控IFN-β的表达尚未明确。本研究假设TRIM2通过与病毒RNA或宿主因子相互作用，影响IFN-β的产生。我们将采用分子生物学、细胞生物学和免疫学方法，探索TRIM2与A型流感病毒诱导IFN-β表达的关系。预期结果将揭示TRIM2在抗病毒免疫反应中的作用，为开发新的抗病毒策略提供理论基础。该研究对理解宿主抗病毒机制具有重要科学意义，并可能对临床治疗流感病毒感染提供新的视角。

AI项目思路：

科学问题：TRIM2如何调控A型流感病毒诱导的IFN-β表达？
前期研究：已有研究表明TRIM2参与抗病毒反应，但其具体机制尚不明确。
研究创新点：本研究将深入探讨TRIM2在IFN-β表达中的直接作用机制。
技术路线：包括病毒学、分子生物学、细胞培养和免疫检测技术。
关键技术：TRIM2与病毒RNA的相互作用分析，IFN-β启动子活性检测。
实验模型：使用A型流感病毒感染的细胞模型进行研究。

AI技术路线图

        graph TD
          A[研究起始] --> B[文献回顾与假设提出]
          B --> C[实验设计与方法学准备]
          C --> D[A型流感病毒感染模型建立]
          D --> E[TRIM2与病毒RNA相互作用分析]
          E --> F[TRIM2对IFN-β启动子活性的影响]
          F --> G[IFN-β表达水平测定]
          G --> H[TRIM2功能丧失与获得研究]
          H --> I[数据收集与分析]
          I --> J[结果解释与科学验证]
          J --> K[研究结论与未来方向]
          K --> L[研究结束]
关闭
close
客服二维码