相关实验视频
Updated: Jul 20, 2025

08:57
Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
Published on: August 14, 2018
16.0K
关于非二进制树调和与内共生基因转移的复杂性
Mathieu Gascon1, Nadia El-Mabrouk2
1Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, Canada.
Algorithms for molecular biology : AMB
|July 30, 2023
概括
将基因和物种树与内共生基因转移 (EGT) 调和起来是复杂的. 这项研究表明,EGT调和问题是NP-完整的,即使对于简单的情况,但为特定场景提供算法.
科学领域:
- 计算生物学 计算生物学
- 生物信息学是一种生物信息学.
- 进化基因组学 进化基因组学
背景情况:
- 将基因树与物种树相协调对于进化研究至关重要.
- 基因转移,特别是横向基因转移 (HGT),使和解复杂化,使其成为NP-hard.
- 线粒体和核基因组之间的内共生基因转移 (EGT) 是一个独特的挑战.
研究的目的:
- 调查在存在内共生基因转移 (EGT) 的情况下,调和多分支基因树与二进制物种树的计算复杂性.
- 开发算法方法来推断最节的重复,损失和EGT (DLE) 调和,用于多分支基因树的二进制改进.
- 分析分配基因标签 (线粒体或核) 的复杂性,以尽量减少EGT事件.
主要方法:
- 提出了一种两步方法:首先,二进制分辨率最大限度地减少重复和损失 (DL) 协调,然后分配叶子标签以最大限度地减少EGT事件.
- 分析了标签分配子问题的复杂性,证明它是NP完整的.
- 开发了一个一般的算法来单独解决多项式,是单元成本的最佳,并为特定情况下提出了一个多项式时间算法.
主要成果:
- 推断 EGT 具有多分支基因树的最节的 DLE 和解的问题是 NP 完整的.
- 这种NP完整性甚至适用于有限的情况,例如单个多体或单向转移.
- 针对单元成本的最佳算法和针对特定基因组环境的多项式时间算法得到了推导.
结论:
- 这项研究提供了第一个算法调查,用于多分支基因树的内共生基因转移与内共生基因转移的和解.
- 这些发现突出了EGT在遗传学和解中所带来的计算挑战.
- 开发的算法为这个复杂问题领域内的特定场景提供了实际解决方案.
相关概念视频
Types of Genetic Transfer Between Organisms
28.0K
Genetic transfer occurs when genetic information is passed from one organism to another. It occurs via two mechanisms: vertical gene transfer and horizontal gene transfer. Vertical gene transfer occurs when genetic information is transferred from one generation to the next, which happens much more frequently than horizontal gene transfer. Both sexual and asexual reproduction are forms of vertical gene transfer, where one or more organisms pass some or all of their genome onto their progeny.
28.0K
Evolutionary Relationships through Genome Comparisons
5.8K
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...
5.8K
Phylogenetic Trees
45.5K
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.
45.5K
Export of Mitochondrial and Chloroplast Genes
3.7K
A eukaryotic cell can have up to three different types of genetic systems: nuclear, mitochondrial, and chloroplast. During evolution, organelles have exported many genes to the nucleus; this transfer is still ongoing in some plant species. Approximately 18% of the Arabidopsis thaliana nuclear genome is thought to be derived from the chloroplast’s cyanobacterial ancestor, and around 75% of the yeast genome derived from the mitochondria’s bacterial ancestor. This export has occurred...
3.7K
Horizontal Gene Transfer
40
Horizontal gene transfer (HGT) is a process where genetic material moves between organisms within the same generation, unlike vertical gene transfer, which occurs from parent to offspring. HGT plays a crucial role in microbial evolution, adaptation, and survival, particularly in shared environments like the human gut.Mobile genetic elements such as plasmids, prophages, integrons, insertion sequences, and transposons facilitate this process. HGT occurs through three primary mechanisms:...
40
Overview of Transposition and Recombination
15.7K
Transposons make up a significant part of genomes of various organisms. Therefore, it is believed that transposition played a major evolutionary role in speciation by changing genome sizes and modifying gene expression patterns. For example, in bacteria, transposition can lead to conferring antibiotic resistance. Movement of transposable elements within the genetic pool of pathogenic bacteria can aid in transfer of antibiotic-resistant genetic elements. In eukaryotes, transposons can carry out...
15.7K

