量子算法 de novo DNA 序列组装基于量子走在图形上的量子步行
G D Varsamis1, I G Karafyllidis2, K M Gilkes3
1Department of Electrical and Computer Engineering, Democritus University of Thrace, Xanthi, 67100, Greece.
Bio Systems
|September 21, 2023
概括
我们开发了一种新的量子算法,用于 de novo DNA 序列组装,解决了在重叠图中找到路径的 NP 难题. 这种量子方法为更高效的DNA组装方法提供了潜在的途径.
科学领域:
- 计算生物学 计算生物学
- 量子计算是一种量子计算.
- 生物信息学是一种生物信息学.
背景情况:
- 对于基因组学来说,De novo DNA 序列组装至关重要.
- 这个问题是计算密集的,被归类为NP-hard.
- 目前的方法依赖于在重叠图中找到路径.
研究的目的:
- 开发一个量子算法,用于新的DNA组装.
- 为了利用量子步行,在重叠图中有效地找到路径.
- 探索一个计算上具有挑战性的生物信息学问题的量子解决方案.
主要方法:
- 开发了一种使用量子步行的量子算法.
- 实施了对重叠图形的层次分区策略.
- 对于低等级图形的联合量子步行与高等级图形的量子哈密尔顿路径算法.
- 使用了Qiskit来测试和模拟量子算法.
主要成果:
- 成功测试了分区量子算法.
- 证实了量子哈密尔顿路径算法对高层次层次的正确运行.
- 开发了一个定制的量子步行模拟器,用于在低级图中搜索路径.
结论:
- 拟议的量子方法为高效的 de novo DNA 组装提供了一个潜在的解决方案.
- 这项工作可能成为未来生物信息学实用量子算法的基础.
- 量子计算显示出在序列组装中解决NP-hard问题的前景.
相关概念视频
01:05Maxam-Gilbert Sequencing
11.2K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
11.2K
03:36Genome Annotation and Assembly
18.9K
The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.
18.9K
01:57Sanger Sequencing
754.7K
DNA sequencing is a fundamental technique that is routinely used in the biological sciences. This method can be applied to a range of questions at different scales - from the sequencing of a cloned DNA fragment or the study of a mutation in a gene up to whole-genome sequencing. However, despite the widespread use of sequencing today, it was not until 1977 that Fredrick Sanger and his collaborators developed the chain-termination method to decode DNA sequences. It relies on the separation of a...
754.7K
03:00Next-generation Sequencing
89.8K
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
89.8K
03:21RNA-seq
10.0K
RNA sequencing, or RNA-Seq, is a high-throughput sequencing technology used to study the transcriptome of a cell. Transcriptomics helps to interpret the functional elements of a genome and identify the molecular constituents of an organism. Additionally, it also helps in understanding the development of an organism and the occurrence of diseases.
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
10.0K