• 文献检索
  • 文档翻译
  • 深度研究
  • 学术资讯
  • Suppr Zotero 插件Zotero 插件
  • 邀请有礼
  • 套餐&价格
  • 历史记录
应用&插件
Suppr Zotero 插件Zotero 插件浏览器插件Mac 客户端Windows 客户端微信小程序
定价
高级版会员购买积分包购买API积分包
服务
文献检索文档翻译深度研究API 文档MCP 服务
关于我们
关于 Suppr公司介绍联系我们用户协议隐私条款
关注我们

Suppr 超能文献

核心技术专利：CN118964589B侵权必究
粤ICP备2023148730 号-1Suppr @ 2026

文献检索

告别复杂PubMed语法，用中文像聊天一样搜索，搜遍4000万医学文献。AI智能推荐，让科研检索更轻松。

立即免费搜索

文件翻译

保留排版，准确专业，支持PDF/Word/PPT等文件格式，支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述，25分钟生成高质量综述，智能提取关键信息，辅助科研写作。

立即免费体验

常树宽泛基因组图上的最大得分路径集

Maximum-scoring path sets on pangenome graphs of constant treewidth.

作者信息

Brejová Broňa, Gagie Travis, Herencsárová Eva, Vinař Tomáš

机构信息

Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University in Bratislava, Bratislava, Slovakia.

Faculty of Computer Science, Dalhousie University, Halifax, NS, Canada.

出版信息

Front Bioinform. 2024 Jul 1;4:1391086. doi: 10.3389/fbinf.2024.1391086. eCollection 2024.

DOI:10.3389/fbinf.2024.1391086
PMID:39011297
原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC11246863/
Abstract

We generalize a problem of finding maximum-scoring segment sets, previously studied by Csűrös (IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004, 1, 139-150), from sequences to graphs. Namely, given a vertex-weighted graph and a non-negative startup penalty , we can find a set of vertex-disjoint paths in with maximum total score when each path's score is its vertices' total weight minus . We call this new problem (MSPS). We present an algorithm that has a linear-time complexity for graphs with a constant treewidth. Generalization from sequences to graphs allows the algorithm to be used on pangenome graphs representing several related genomes and can be seen as a common abstraction for several biological problems on pangenomes, including searching for CpG islands, ChIP-seq data analysis, analysis of region enrichment for functional elements, or simple chaining problems.

摘要

我们将Csűrös（《IEEE/ACM计算生物学与生物信息学汇刊》，2004年，第1卷，第139 - 150页）之前研究的寻找最大得分片段集的问题从序列推广到了图。具体而言，给定一个顶点加权图和一个非负的起始惩罚值，当每条路径的得分是其顶点的总权重减去该惩罚值时，我们可以在该图中找到一组顶点不相交的路径，使其总得分最大。我们将这个新问题称为（MSPS）。我们提出了一种算法，对于具有常数树宽的图，该算法具有线性时间复杂度。从序列到图的推广使得该算法可用于表示多个相关基因组的泛基因组图，并且可以被视为泛基因组上几个生物学问题的通用抽象，包括搜索CpG岛、ChIP - seq数据分析、功能元件区域富集分析或简单的连锁问题。

https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/e3965f25720f/fbinf-04-1391086-g006.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/5837a62084f5/fbinf-04-1391086-g001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/dba556b36f3a/fbinf-04-1391086-g002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/db2afedaa62c/fbinf-04-1391086-g003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/7c4fd6f028fa/fbinf-04-1391086-g004.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/c5e7fe87e1bd/fbinf-04-1391086-g005.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/e3965f25720f/fbinf-04-1391086-g006.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/5837a62084f5/fbinf-04-1391086-g001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/dba556b36f3a/fbinf-04-1391086-g002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/db2afedaa62c/fbinf-04-1391086-g003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/7c4fd6f028fa/fbinf-04-1391086-g004.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/c5e7fe87e1bd/fbinf-04-1391086-g005.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/455f/11246863/e3965f25720f/fbinf-04-1391086-g006.jpg

相似文献

1
Maximum-scoring path sets on pangenome graphs of constant treewidth.常树宽泛基因组图上的最大得分路径集
Front Bioinform. 2024 Jul 1;4:1391086. doi: 10.3389/fbinf.2024.1391086. eCollection 2024.
2
Co-linear chaining on pangenome graphs.泛基因组图谱上的共线性连锁
Algorithms Mol Biol. 2024 Jan 27;19(1):4. doi: 10.1186/s13015-024-00250-w.
3
Querying graphs in protein-protein interactions networks using feedback vertex set.使用反馈顶点集查询蛋白质-蛋白质相互作用网络中的图。
IEEE/ACM Trans Comput Biol Bioinform. 2010 Oct-Dec;7(4):628-35. doi: 10.1109/TCBB.2010.53.
4
Gap-Sensitive Colinear Chaining Algorithms for Acyclic Pangenome Graphs.循环无亲缘基因组图谱的缝隙敏感共线性链接算法。
J Comput Biol. 2023 Nov;30(11):1182-1197. doi: 10.1089/cmb.2023.0186. Epub 2023 Oct 30.
5
Complexity of Secure Sets.安全集的复杂性
Algorithmica. 2018;80(10):2909-2940. doi: 10.1007/s00453-017-0358-5. Epub 2017 Aug 14.
6
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.用于寻找大型诱导稀疏子图的亚指数时间算法。
Algorithmica. 2021;83(8):2634-2650. doi: 10.1007/s00453-020-00745-z. Epub 2020 Jul 31.
7
Pangenome comparison via ED strings.通过编辑距离字符串进行泛基因组比较。
Front Bioinform. 2024 Sep 26;4:1397036. doi: 10.3389/fbinf.2024.1397036. eCollection 2024.
8
Efficient short read mapping to a pangenome that is represented by a graph of ED strings.高效的短读映射到由 ED 字符串图表示的泛基因组。
Bioinformatics. 2023 May 4;39(5). doi: 10.1093/bioinformatics/btad320.
9
Pangenome graphs in infectious disease: a comprehensive genetic variation analysis of leveraging Oxford Nanopore long reads.传染病中的泛基因组图谱：利用牛津纳米孔长读长进行的全面遗传变异分析
Front Genet. 2023 Aug 10;14:1225248. doi: 10.3389/fgene.2023.1225248. eCollection 2023.
10
Detecting high-scoring local alignments in pangenome graphs.在泛基因组图中检测高分局部比对。
Bioinformatics. 2021 Aug 25;37(16):2266-2274. doi: 10.1093/bioinformatics/btab077.

本文引用的文献

1
Co-linear chaining on pangenome graphs.泛基因组图谱上的共线性连锁
Algorithms Mol Biol. 2024 Jan 27;19(1):4. doi: 10.1186/s13015-024-00250-w.
2
Chaining for accurate alignment of erroneous long reads to acyclic variation graphs.基于无环变异图的错误长读精确比对链。
Bioinformatics. 2023 Aug 1;39(8). doi: 10.1093/bioinformatics/btad460.
3
Detecting clusters of transcription factors based on a nonhomogeneous poisson process model.基于非齐次泊松过程模型的转录因子簇检测。
BMC Bioinformatics. 2022 Dec 9;23(1):535. doi: 10.1186/s12859-022-05090-2.
4
Treewidth-based algorithms for the small parsimony problem on networks.基于树宽的网络上小简约问题的算法
Algorithms Mol Biol. 2022 Aug 20;17(1):15. doi: 10.1186/s13015-022-00216-w.
5
Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics.树形分解：降低树宽以解锁RNA生物信息学中的固定参数可解算法
Algorithms Mol Biol. 2022 Apr 2;17(1):8. doi: 10.1186/s13015-022-00213-z.
6
The design and construction of reference pangenome graphs with minigraph.使用 Minigraph 设计和构建参考泛基因组图谱。
Genome Biol. 2020 Oct 16;21(1):265. doi: 10.1186/s13059-020-02168-z.
7
Distance indexing and seed clustering in sequence graphs.序列图中的距离索引和种子聚类。
Bioinformatics. 2020 Jul 1;36(Suppl_1):i146-i153. doi: 10.1093/bioinformatics/btaa446.
8
A genome-wide scan statistic framework for whole-genome sequence data analysis.全基因组序列数据分析的全基因组扫描统计框架。
Nat Commun. 2019 Jul 9;10(1):3018. doi: 10.1038/s41467-019-11023-0.
9
Graph Peak Caller: Calling ChIP-seq peaks on graph-based reference genomes.图峰调用器：基于图的参考基因组上的 ChIP-seq 峰调用。
PLoS Comput Biol. 2019 Feb 19;15(2):e1006731. doi: 10.1371/journal.pcbi.1006731. eCollection 2019 Feb.
10
Variation graph toolkit improves read mapping by representing genetic variation in the reference.变异图谱工具包通过表示参考中的遗传变异来提高读映射质量。
Nat Biotechnol. 2018 Oct;36(9):875-879. doi: 10.1038/nbt.4227. Epub 2018 Aug 20.