寻找基因网络之间的最大共同收缩
Bertrand Marchand1, Nadia Tahiri2, Shohreh Golpaigani Fard3
1Departement d'Informatique, University of Sherbrooke, 2500 Boulevard de l'Universite, J1K2R1, Sherbrooke, QC, Canada. bertrand.marchand@usherbrooke.ca.
Algorithms for molecular biology : AMB
|October 2, 2025
概括
本研究引入了一个操作距离,用于比较使用边缘收缩和扩张的遗传学网络. 它证明了这个距离是NP-难以计算的,但为弱树提供了多项式时间解决方案.
科学领域:
- 计算生物学 计算生物学
- 人类遗传学 是一个学科.
- 图形理论 图形理论
背景情况:
- 遗传树是进化生物学中的基础.
- 比较家族遗传网络需要强大的方法.
- 现有的树木比较方法,如罗宾逊-福尔兹,需要适应网络.
研究的目的:
- 定义和分析植物遗传网络的操作距离.
- 为了研究比较家族遗传网络的计算复杂性.
- 探索特定网络类型的算法解决方案.
主要方法:
- 使用边缘收缩和扩张定义家族遗传网络比较.
- 证明这些操作下的网络空间的连接性.
- 分析计算最大常见收缩的复杂性.
- 开发特定网络类别的算法.
主要成果:
- 边缘收缩和扩张连接了家族遗传网络的空间.
- 基于这些编辑操作,可以定义一个操作距离.
- 计算最大常见收缩是NP难的,即使有有限的参数.
- 这个问题的下限是使用指数时间假设建立的.
- 一个多项式时代算法是为弱树的呈现.
结论:
- 拟议的操作距离为比较族系遗传网络提供了一种新的方式.
- NP-硬度结果突出了网络比较中的计算挑战.
- 弱树算法为相关网络类提供了一个实用的解决方案.
- 这项工作有助于通过网络分析了解进化关系.
相关概念视频
02:54Evolutionary Relationships through Genome Comparisons
6.9K
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...
6.9K
03:21Phylogenetic Trees
49.2K
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.
49.2K
01:23Phylogeny
56.8K
Phylogeny is concerned with the evolutionary diversification of organisms or groups of organisms. A group of organisms with a name is called a taxon (singular). Taxa (plural) can span different levels of the evolutionary hierarchy. For instance, the group containing all birds is a taxon (comprising the class Aves), and the group of all species of daisies (the genus Bellis) is a taxon. Phylogenies can likewise include just one genus (i.e., depict species relationships) or span an entire kingdom.
56.8K
02:05Gene Evolution - Fast or Slow?
8.0K
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...
8.0K
02:05Gene Evolution - Fast or Slow?
3.4K
3.4K
01:24Sequence Networks of Rotating Machines
485
A Y-connected synchronous generator, grounded through a neutral impedance, is designed to produce balanced internal phase voltages with only positive-sequence components. The generator's sequence networks include a source voltage that is exclusively in the positive-sequence network. The sequence components of line-to-ground voltages at the generator terminals illustrate this configuration.
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
485