通过转换进一步接近排序的障碍.
Luiz A G Silva1, Luis A B Kowada2, Maria E M T Walter1
1Departamento de Ciência da Computação, Universidade de Brasília, Brasília, Brazil.
概括
这项研究确定了"palisades" permutations的转换距离,为3个 permutations (TD3) 提供了准确的转换直径. 这解决了长期存在的问题,并影响了基因组重组的近似算法.
科学领域:
- 计算生物学 计算生物学
- 基因组学就是基因组学.
- 组合学是一种组合学.
背景情况:
- 转移距离问题是基因组重排的基本问题.
- 通过转换进行排序 (SBT) 是这个领域的一个关键问题.
- 众所周知,Palisades对于SBT来说是困难的排列.
研究的目的:
- 为了确定杆的转移距离.
- 为了提供对3次变换 (TD3) 的确切转换直径.
- 分析对SBT近似算法的影响.
主要方法:
- 调查杆,一个难以分类的 permutations的家庭.
- 计算这些 permutations 的转位距离.
- 使用巴夫纳-佩夫纳尔下界.
主要成果:
- 确定了3个变换 (TD3) 的确切转换直径.
- 通过使用巴夫纳-佩夫纳下界,证明SBT的近似比率不能保证在1.375以下.
- 这一发现对SBT的研究有重大影响.
结论:
- 护的转移距离已经准确计算出来.
- 已经确定了TD3的确切值,解决了已知的研究缺口.
- 这项研究提供了关键的洞察力,了解通过转换进行排序的近似算法的局限性.
相关概念视频
Routh-Hurwitz Criterion II
260
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
260
Overview of Transposition and Recombination
15.6K
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.6K
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.1K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.1K
Theorems of Pappus and Guldinus: Problem Solving
747
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
747
Castigliano's Theorem: Problem Solving
663
The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam...
663
Transposons
39
Transposons, or "jumping genes," are small mobile genetic elements (MGEs) that range from 700 to 40,000 base pairs in length. They are found in all organisms and can move within the same chromosome or transfer to different chromosomes. In some cases, transposons can also jump between different host DNA molecules, such as plasmids or viruses, contributing to genetic variability.Barbara McClintock first discovered these mobile genetic elements in the 1940s while studying maize genetics, and she...
39


