在-mers的最大独立集合上,使用编辑距离
Leran Ma1, Ke Chen2, Mingfu Shao3
1The Pennsylvania State University Schreyer Honors College Department of Computer Science and Engineering State College, United States.
概括
本研究探讨了使用最大独立集 (MIS) 进行高效数据素描的k-mers的度量空间. 介绍了三种新的算法,用于在大k-mer空间中找到MIS,改进了计算生物学分析.
科学领域:
- 计算生物学 计算生物学
- 生物信息学是一种生物信息学.
- 数据科学数据科学数据科学
背景情况:
- K-mers和编辑距离是计算生物学中的核心概念.
- 编辑距离的k-mers的度量空间未被充分探索.
- 最大独立集 (MIS) 提供了稀疏的,理论上是 k-mer 空间的正确草图.
研究的目的:
- 通过使用MIS来研究k-mer空间的结构.
- 开发高效的算法,以在大型k-mer空间中找到MIS.
- 为了使集群,索引和草图测序数据中的关键应用程序.
主要方法:
- 一个贪的算法用于MIS识别.
- 一个优化的算法利用本地和编辑距离的边界.
- 一种基于图形的方法,将编辑距离转换为最短路径问题.
- 对k至15的算法进行实现和分析.
主要成果:
- 成功计算了k-mer空间的MIS,直至k=15.
- 证明了拟议算法的可行性和效率.
- 提供了计算MIS的统计属性的分析.
结论:
- 开发的算法为在k-mer空间中构建MIS提供了高效的方法.
- MIS对于绘制和分析大规模测序数据,特别是具有高错误率的数据非常有价值.
- 这项研究有助于更好地了解k-mer的尺度空间结构.
相关概念视频
Multi-species Conserved Sequences
3.9K
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
3.9K
Restriction Enzymes
30.7K
Restriction enzymes are bacterial enzymes used to cut DNA in a sequence-specific manner. To cleave DNA, they bind to specific palindromic sequences called restriction sites. Such palindromic DNA sequences or inverted repeats are commonly found in regions of functional significance, such as the origin of replication, gene operator sites, and regions containing transcription termination signals.
The host bacteria protect their own genomic DNA from these enzymes by methylating these sites. Some...
The host bacteria protect their own genomic DNA from these enzymes by methylating these sites. Some...
30.7K
Law of Independent Assortment
55.8K
While Mendel’s Law of Segregation states that the two alleles for one gene are separated into different gametes, a different question of how different genes are inherited remains. For example, is the gene for tall plants inherited with the gene for green peas? Mendel asked this question by experimenting with a dihybrid cross; a cross in which both parents are homozygous for two distinct traits resulting in an F1 generation that are heterozygous for both traits.
55.8K
Maxam-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
Kendall's Coefficient of Concordance
348
Kendall's Coefficient of Concordance (W), also known as Kendall's W, is a non-parametric statistical measure used to assess the agreement or concordance between multiple raters or judges when they rank a set of items. It is often used when you have ordinal data (ranks) and you want to see if there is consistency or consensus among the raters. It is widely applied in research areas such as psychology, medicine, and social sciences, where multiple judges are asked to rank or rate subjects...
348
Second Uniqueness Theorem
1.0K
Consider a region consisting of several individual conductors with a definite charge density in the region between these conductors. The second uniqueness theorem states that if the total charge on each conductor and the charge density in the in-between region are known, then the electric field can be uniquely determined.
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
1.0K


