相关实验视频

Updated: Jun 12, 2025

Rare Event Detection Using Error-corrected DNA and RNA Sequencing

Rare Event Detection Using Error-corrected DNA and RNA Sequencing

Published on: August 3, 2018

一个平均情况高效的两阶段算法,用于列举基因组对之间所有最小长度的最长常见子字符串

Mattia Prosperi¹, Simone Marini¹, Christina Boucher²

¹dept. of Epidemiology, University of Florida, Gainesville, FL (USA).

Proceedings. IEEE International Conference on Healthcare Informatics

|September 23, 2024

概括

本研究介绍了一种有效的算法,用于在大型生物文本中找到所有最小长度的最长常见子字符串 (ALCS). 这种新方法为基因组分析提供了显著的速度优势,特别是在不同的基因组中.

科学领域:

生物信息学是一种生物信息学.
计算生物学计算生物学
基因组学就是基因组学.

背景情况:

最长的共同子串 (LCS) 问题是生物信息学中的基本问题.
列出最小长度的所有最长常见子字符串 (ALCS) 对于发现基因特征在诸如基因组和元基因组等大型生物文本中至关重要.
对于非常长的序列,现有的方法可能没有效率.

研究的目的:

为ALCS-k问题开发一个高效的两阶段算法,该算法列举了至少长度为k的所有常见子字符串.
为分析大型基因组和元基因组数据集提供可扩展的解决方案.
通过发现遗传特征,提供对生物机制的洞察.

主要方法:

介绍了一种新的两阶段算法,利用k-mers (长度为k的子字符串) 的光谱.
第一个阶段涉及高效的k-mer频谱分析与日志线性时间复杂度.
第二阶段专注于识别具有平均案例日志线性时间复杂性的常见k-mers,大大减少了搜索空间.

主要成果:

该算法在第一阶段的k-mers数量中实现了日志线性时间复杂性,在第二阶段的普通k-mers数量中实现了平均情况日志线性时间复杂性.
空间复杂性在第一阶段 (基于磁盘) 是线性的,在第二阶段 (基于磁盘和内存) 是平均线性的.
对各种基因组的实证测试表明运行时间与理论估计一致,并显示出不同基因组的MUMmer4比MUMmer4具有非对称的优势.

结论:

拟议的ALCS-k算法对于分析大型生物序列是高效且可扩展的.
它为识别遗传特征和理解生物机制提供了有价值的工具.
该方法与MUMmer4等现有工具相比,表现出优异的性能,特别是在不同的基因组中.

关键词:

算法算法是一种算法.生物信息学是一种生物信息学.生物序列生物序列生物序列计算生物学计算生物学

更多相关视频

G2-seq: A High Throughput Sequencing-based Technique for Identifying Late Replicating Regions of the Genome

G2-seq: A High Throughput Sequencing-based Technique for Identifying Late Replicating Regions of the Genome

Published on: March 22, 2018

Detection of Rare Genomic Variants from Pooled Sequencing Using SPLINTER

Detection of Rare Genomic Variants from Pooled Sequencing Using SPLINTER

Published on: June 23, 2012

相关概念视频

Evolutionary Relationships through Genome Comparisons

Evolutionary Relationships through Genome Comparisons

Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...

Genome Annotation and Assembly

Genome Annotation and Assembly

The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.