如何找到长的最大精确匹配,并忽略短的匹配
1Faculty of Computer Science, Dalhousie University, Halifax, Canada.
概括
这项研究提出了一种有效的算法,用于在大型生物数据集中找到长最大精确匹配 (MEM). 该方法使用一个紧的文本索引,大大加快了对泛基因组参考的分析.
科学领域:
- 生物信息学是一种生物信息学.
- 计算生物学 计算生物学
- 基因组学就是基因组学.
背景情况:
- 最大精确匹配 (MEMs) 对于序列对齐和分析至关重要.
- 泛基因参考对传统的字符串匹配算法构成挑战.
- 识别统计学意义上的MEM是现代遗传研究的关键.
研究的目的:
- 开发一种高效的算法,用于在大型文本中找到长的MEM.
- 调整字符串匹配技术,以适应泛基因参考的复杂性.
- 为了优化对统计学上显著的最大精确匹配的搜索.
主要方法:
- 使用一个紧的索引为文本.
- 实现一个算法来找到所有特定最小长度的MEM.
- 分析与模式和文本长度以及MEM特征相关的时间复杂性.
主要成果:
- 该算法在O(m+n) 时间内找到所有长度至少为k的MEM.
- 额外的时间与长于近k的MEM数量成正比.
- 这种方法适用于大规模的泛基因组数据集.
结论:
- 拟议的方法有效地识别了显著的最大精确匹配.
- 这种算法非常适合泛基因组生物信息学的需求.
- 这些发现为分析大量遗传序列数据提供了实用解决方案.
相关概念视频
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
Maxam-Gilbert Sequencing
11.1K
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.1K
Long-patch Base Excision Repair
7.0K
Since the discovery of the two BER pathways, there has been a debate about how a cell chooses one pathway over the other and the factors determining this selection. Numerous in vitro experiments have pointed out multiple determinants for the sub-pathway selection. These are:
7.0K
Multiple Comparison Tests
3.9K
Multiple comparison test, abbreviated as MCT, is a post hoc analysis generally performed after comparing multiple samples with one or more tests. An MCT will help identify a significantly different sample among multiple samples or a factor among multiple factors.
It would be easy to compare two samples using a significance alpha level of 0.05. In other words, there is only one sample pair to be compared. However, it would be difficult to identify a significantly different sample if the number...
It would be easy to compare two samples using a significance alpha level of 0.05. In other words, there is only one sample pair to be compared. However, it would be difficult to identify a significantly different sample if the number...
3.9K
RACE - Rapid Amplification of cDNA Ends
6.3K
Rapid Amplification of cDNA Ends, or RACE, is one of the most effective methods to obtain a full-length cDNA from an mRNA sequence between a known internal region to the unknown sequence at the 5’ or 3’ end. The unknown region is cloned in the cDNA by a gene-specific primer that binds the known end, and a hybrid primer that attaches a predefined anchor sequence to the unknown end of the cDNA. The sequence in between is amplified by PCR with an anchor primer and a gene-specific...
6.3K
Mismatch Repair
4.8K
Organisms are capable of detecting and fixing nucleotide mismatches that occur during DNA replication. This sophisticated process requires identifying the new strand and replacing the erroneous bases with correct nucleotides. Mismatch repair is coordinated by many proteins in both prokaryotes and eukaryotes.
The Mutator Protein Family Plays a Key Role in DNA Mismatch Repair
The human genome has more than 3 billion base pairs of DNA per cell. Prior to cell division, that vast amount of genetic...
The Mutator Protein Family Plays a Key Role in DNA Mismatch Repair
The human genome has more than 3 billion base pairs of DNA per cell. Prior to cell division, that vast amount of genetic...
4.8K


