搜索计划的近似字符串匹配
Simon Gene Gottlieb1, Knut Reinert1,2
1Informatik & Mathematik, Freie Universität Berlin, Takustraße 9, 14195 Berlin, Germany.
NAR genomics and bioinformatics
|March 19, 2025
概括
这项研究统一了使用搜索方案的近似搜索策略,开发了一种新的启发式,可以提高多个错误的性能. 它还引入了加权节点计数指标,以更准确地评估性能.
科学领域:
- 计算生物学 计算生物学
- 生物信息学是一种生物信息学.
- 弦学是指弦学中的一些学科.
背景情况:
- 与全文索引的近似字符串匹配对于生物信息学至关重要.
- 现有的搜索方案提供了加快速度,但为多个错误找到最佳方案是具有挑战性的.
研究的目的:
- 在搜索计划框架内统一和扩展现有的近似搜索策略.
- 开发一个改进的启发式来构建搜索方案,特别是对于更高的错误数量.
- 为搜索算法提出一个更准确的性能指标.
主要方法:
- 将现有的近似搜索策略 (后过器,01*0种子, pigeonhole原则) 建模为搜索方案.
- 开发一种新的启发式,用于构建适用于任意数量的错误的搜索方案.
- 引入和评估"加权节点数"作为性能指标.
主要成果:
- 在搜索方案框架下统一多样化的搜索策略,为任何错误计数提供新的方案.
- 开发了一个启发式搜索方案构建,匹配最佳方案,并改善节点数>=4个错误.
- 证明了节点计数的局限性,并验证了加权节点计数指标的准确性.
结论:
- 搜索方案为近似字符串匹配提供了一个统一的框架.
- 新的启发式设计为复杂的错误场景提供了高效的搜索方案构建.
- 权重节点数量指标为搜索算法提供了更现实的性能评估.
相关概念视频
Mismatch Repair
39.8K
Overview
39.8K
DNA Base Pairing
26.6K
Erwin Chargaff’s rules on DNA equivalence paved the way for the discovery of base pairing in DNA. Chargaff’s rules state that in a double-stranded DNA molecule,
26.6K
¹H NMR Chemical Shift Equivalence: Homotopic and Heterotopic Protons
2.3K
Protons in identical electronic environments within a molecule are chemically equivalent and have the same chemical shift. The replacement test is a useful tool to identify chemical equivalence and predict NMR spectra. A substituent replaces each of the protons being examined and the resulting molecules are compared. If the same molecule is obtained, the protons are equivalent or homotopic. Replacement of any hydrogens in ethane by chlorine yields chloroethane because all six protons are...
2.3K
¹H NMR: Pople Notation
1.7K
The Pople nomenclature system classifies spin systems based on the difference between their chemical shifts. Coupled spins are denoted by capital letters with subscripts indicating the number of equivalent nuclei. When the coupled nuclei have well-separated chemical shifts, they are assigned letters that are far apart in the alphabet, such as A and X. When the difference in chemical shifts is small, coupled nuclei are named using adjacent letters of the alphabet (AB, MN, or XY).
A proton...
A proton...
1.7K
Maxam-Gilbert Sequencing
10.8K
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...
10.8K


