更快地计算左边最短的唯一子字符串
Larissa L M Aguiar1, Felipe A Louza2
1Faculdade de Engenharia Elétrica, Universidade Federal de Uberlândia, Uberlândia, MG, Brazil.
Algorithms for molecular biology : AMB
|June 20, 2025
概括
本研究介绍了一种有效的算法,用于找到左边最短的唯一子字符串 (LSUS),这对于PCR原始设计等应用至关重要. 新方法比现有方法更快,提供了实际的速度改进.
科学领域:
- 字符串处理算法 字符串处理算法
- 生物信息学应用程序
- 计算生物学是一种计算生物学.
背景情况:
- 最短的唯一子字符串 (SUS) 是字符串处理中的一个关键问题.
- 应用包括生物信息学,如DNA序列分析.
- 一个特定的变体,左边最短的唯一子字符串 (LSUS),对于PCR原始设计至关重要.
研究的目的:
- 为LSUS问题提供一种新,高效的算法.
- 解决生物信息学中更快的计算方法的需求.
- 为PCR原料设计挑战提供实用解决方案.
主要方法:
- 为LSUS开发了一种线性时间O (n) 算法.
- 使用了2n个内存单词加上n个字节的输入字符串.
- 为高效的字符串处理而设计的算法.
主要成果:
- 实现了O (n) 时间复杂度.
- 演示了实际的速度改进,平均比相关方法快两倍.
- 保持了与现有算法相比较的峰值内存足迹.
结论:
- 提出的LSUS算法在时间复杂性方面非常高效.
- 为生物信息学任务提供实用优势,特别是PCR原料设计.
- 在有效地解决LSUS问题方面取得了重大进展.
相关概念视频
Maxam-Gilbert Sequencing
11.5K
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.5K
Lagging Strand Synthesis
54.4K
During replication, the complementary strands in double-stranded DNA are synthesized at different rates. Replication first begins on the leading strand. Replication starts later, occurs more slowly, and proceeds discontinuously on the lagging strand.
There are several major differences between synthesis of the leading strand and synthesis of the lagging strand. 1) Leading strand synthesis happens in the direction of replication fork opening, whereas lagging strand synthesis happens in the...
There are several major differences between synthesis of the leading strand and synthesis of the lagging strand. 1) Leading strand synthesis happens in the direction of replication fork opening, whereas lagging strand synthesis happens in the...
54.4K
Second Uniqueness Theorem
1.1K
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.1K
Restriction Enzymes
31.5K
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...
31.5K
Predicting Products: Substitution vs. Elimination
12.3K
When a nucleophile and an alkyl halide react, nucleophilic substitution and β-elimination reactions compete to generate products.
The following factors can influence the mechanisms competing against each other:
The following factors can influence the mechanisms competing against each other:
12.3K
Multi-species Conserved Sequences
4.3K
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...
4.3K


