重建过去的indels的算法:只有删除的节问题
Jordan Moutet1, Eric Rivals1, Fabio Pardi1
1LIRMM, Université de Montpellier, CNRS, Montpellier, France.
PLoS computational biology
|July 28, 2025
概括
祖先序列的重建是具有挑战性的. 本研究介绍了一个仅删除的模型,具有最优的重建的精确算法和显示不确定性的图形表示.
科学领域:
- 生物信息学是一种生物信息学.
- 计算生物学 计算生物学
- 进化生物学 进化生物学
背景情况:
- 祖先序列重建对于理解蛋白质工程和基因组进化至关重要.
- 现有的算法有效地处理替换,但与插入和删除 (indels) 斗争.
- 目前的方法缺少多项式时间精确解决方案,用于包括内置的重建和有效的不确定性表示.
研究的目的:
- 开发一种有效的方法,用于仅考虑删除的祖先序列重建.
- 为寻找所有最佳重建提供一个精确的算法.
- 用数学证明的图表来表示祖先重建中的不确定性.
主要方法:
- 开发了一个精确的算法,用于祖先序列重建,只允许删除.
- 分析了计算复杂性,实现了单个最佳解决方案检索的多项式时间.
- 构建了一个图表来表示给定节点的所有最佳重建.
主要成果:
- 创建了一个精确的算法,以在仅删除模型下找到所有最佳祖先重建.
- 算法在寻找单个最佳解决方案时以多项式时间运行.
- 为所有最佳重建开发了一种新的基于图形的表示,使用数学严谨度.
结论:
- 只有删除模型为祖先序列重建挑战提供了一种可处理的方法.
- 开发的算法和图形表示有效地解决了计算复杂性和不确定性.
- 这项工作为更复杂的,有意识的重建方法提供了基础.
相关概念视频
Gene Duplication and Divergence
6.3K
The seminal work of Ohno in 1970 popularized the idea of gene duplication and divergence. DNA sequence comparison studies reveal that a large portion of the genes in bacteria, archaebacteria, and eukaryotes was generated by gene duplication and divergence, indicating its critical role in evolution.
The duplicated copies of the gene are called Paralogs. Paralogs with similar sequences and functions form a gene family. Across several species, a large number of gene families are...
The duplicated copies of the gene are called Paralogs. Paralogs with similar sequences and functions form a gene family. Across several species, a large number of gene families are...
6.3K
Restriction Enzymes
31.3K
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.3K
Conservative Site-specific Recombination and Phase Variation
6.1K
Because the DNA segments are cut and reorganized in a direction-specific manner, site-specific recombination has emerged as an efficient genetic engineering technique. Flippase and Cyclization recombinases or Flp and Cre, respectively, are two members of the tyrosine recombinase family derived from bacteriophages, that are used to mediate site-specific DNA insertions, deletions, and targeted expression of proteins in mammalian cell lines.
The recognition sites for Cre recombinase called LoxP...
The recognition sites for Cre recombinase called LoxP...
6.1K
DNA Isolation
40.5K
DNA isolation protocols can be fast and straightforward or complex and time-consuming depending on the type and quality of DNA required for further processing. For example, plasmid DNA extraction is a bit more complicated than genomic DNA extraction because of the need for an appropriate lysis method to separate plasmid DNA from gDNA during isolation. However, for specific applications, such as long-range DNA sequencing that require a good yield of high- quality DNA samples, we need to follow...
40.5K
Single Nucleotide Polymorphisms-SNPs
15.9K
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.9K
Restarting Stalled Replication Forks
5.9K
DNA replication is initiated at sites containing predefined DNA sequences known as origins of replication. DNA is unwound at these sites by the minichromosome maintenance (MCM) helicase and other factors such as Cdc45 and the associated GINS complex.The unwound single strands are protected by replication protein A (RPA) until DNA polymerase starts synthesizing DNA at the 5’ end of the strand in the same direction as the replication fork. To prevent the replication fork from falling apart,...
5.9K


