最小的定位子链覆盖是李和斯蒂芬斯模型的另类类型线程替代方案
Ahsan Sanaullah1, Degui Zhi2, Shaojie Zhang3
1Department of Computer Science, University of Central Florida, Orlando, Florida 32816, USA.
Genome research
|June 14, 2023
概括
我们引入了一种新的方法,最小位置子链覆盖 (MPSC),用于在大型生物银行规模面板中复原型重建. 这种方法提供了高效的单 haplotype 线程,并通过揭示数据特征来改善基因型赋值.
科学领域:
- 遗传学 是一个遗传学.
- 计算生物学 计算生物学
- 生物信息学是一种生物信息学.
背景情况:
- 李和斯蒂芬斯 (LS) 隐藏的马尔科夫模型 (HMM) 对于类型重建是有效的,但由于线性时间复杂性,对于大型参考面板是无效的.
- 模式二进制搜索树 (PBWT) 通过有效地识别本地单元型匹配,为LS HMM提供了更快的方法.
研究的目的:
- 介绍关于最小位置子串覆盖 (MPSC) 问题的解决空间的新发现.
- 开发MPSC的最佳算法,包括计数,长度最大和h-MPSC解决方案.
- 揭示LS模型的大型面板的解决方案空间,并改进基因型归算.
主要方法:
- 作为最小位置子串覆盖 (MPSC) 问题,制定了单 haplotype 重建.
- 开发了MPSC的最佳算法,包括解决方案计数和长度最大和h-MPSC等变化.
- 分析了MPSC的大型生物银行规模面板的解决方案空间.
主要成果:
- MPSC的配方使得随样本大小 (O(N) 的时间复杂度常数的哈普罗型线程成为可能,这使得它对大型面板来说是可行的.
- 新的算法为MPSC解决方案空间提供了洞察力,并揭示了生物库规模数据集的特征.
- 拟议的方法显示了提高基因型归算准确性的潜力.
结论:
- MPSC问题为LS HMM提供了一个可扩展的替代方案,用于在大数据集中复原型重建.
- 开发的算法有效地探索MPSC解决方案空间,并为遗传数据提供有价值的见解.
- 这种方法增强了基因型归算,并有助于理解大规模基因组数据的特征.
相关概念视频
Position-effect Variegation
6.4K
In 1928, a German botanist Emil Heitz observed the moss nuclei with a DNA binding dye. He observed that while some chromatin regions decondense and spread out in the interphase nucleus, others do not. He termed them euchromatin and heterochromatin, respectively. He proposed that the heterochromatin regions reflect a functionally inactive state of the genome. It was later confirmed that heterochromatin is transcriptionally repressed, and euchromatin is transcriptionally active chromatin.
6.4K
Single Nucleotide Polymorphisms-SNPs
15.3K
A single nucleotide polymorphism or SNP is a single nucleotide variation at a specific genomic position in a large population. It is the most prevalent type of sequence variation found in the human genome. Point mutations that occur in more than 1% of the population qualify as SNPs. These are present once every 1000 nucleotides on an average in the human genome. Replacement of a purine with another purine (A/G) or a pyrimidine with another pyrimidine (C/T) is known as a transition. In contrast,...
15.3K
Modern Molecular Taxonomy
56
Advancements in molecular biology have revolutionized the identification and characterization of bacteria, with multiple methods leveraging DNA sequencing for enhanced precision. As sequencing technologies improve and costs decline, these approaches are increasingly used in clinical, environmental, and evolutionary studies.Multilocus Sequence Typing (MLST) examines several housekeeping genes, essential chromosomal genes encoding cellular functions, to distinguish strains. Approximately...
56
Sanger Sequencing
755.1K
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...
755.1K
Comparing Copy Number Variations and SNPs
17.8K
Sequencing of the human genome has opened up several best-kept secrets of the genome. Scientists have identified thousands of genome variations that exist within a population. These variations can be a single nucleotide or a larger chromosomal variation.
Copy number variations or CNVs are the structural variations that cover more than 1kb of DNA sequence. The single nucleotide polymorphism (SNP), on the other hand, is a single nucleotide change or a point mutation that is found in more than 1%...
Copy number variations or CNVs are the structural variations that cover more than 1kb of DNA sequence. The single nucleotide polymorphism (SNP), on the other hand, is a single nucleotide change or a point mutation that is found in more than 1%...
17.8K
Per-Unit Sequence Models
99
An ideal Y-Y transformer, grounded through neutral impedances, displays per-unit sequence networks akin to those of a single-phase ideal transformer when subjected to balanced positive- or negative-sequence currents. These currents do not produce neutral currents, and their associated voltage drops.
Zero-sequence currents, which are identical in magnitude and phase, generate a neutral current, resulting in voltage drops across the neutral impedance and the low-voltage winding. If the...
Zero-sequence currents, which are identical in magnitude and phase, generate a neutral current, resulting in voltage drops across the neutral impedance and the low-voltage winding. If the...
99


