【摘 要】
:
Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions. Namely, given any two permutations, f
【机 构】
:
Department of Mathematics
论文部分内容阅读
Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions. Namely, given any two permutations, find the shortest distance between them. This problem is related with genome rearrangement. The sorting of signed permutations is studied. Because in genome rearrangement, genes are oriented in DNA sequences. The transpositions which have been studied in the literature can be viewed as operations working on two consecutive segments of the genome. In this paper, a new kind of transposition which can work on two arbitrary segments of the genome is proposed, and the sorting of signed permutations by reversals and this new kind of transpositions are studied. After establishing a lower bound on the number of operations needed, a 2-approximation algorithm is presented for this problem and an example is given to show that the performance ratio of the algorithm cannot be improved.
其他文献
Stable and well-dispersed poly(N-vinyl-2-pyrrolidone) (PVP)-stabilized ruthenium colloidal clusters were prepared via the reduction of ruthenium(Ⅲ) chloride by
We discussed the directed motion and the energy conversion efficiency of a particle in two-state ratchet potentials with white noise. We studied the effective p
We investigate the coherent tunneling phenomenon of the laser-driven atomic ensembles confined in a well-separated double-well potential. By generalizing the Fr
Consider a backward heat equation in a bounded domain Ω R2 with the noisy data in theinitial time geometry. The aim is to find the temperature for 0 <ε< t < T. F
The chemical structure of an exopolysaecharide (EPS) produced by Sorangium cellulosum NUST06 was investigated. The EPS was found to have molecular masses greate
This paper reports the electrochemical properties of sulpiride at a mercury electrode, especially its adsorptive characteristic. Sulpiride dissolved in a suppor
In order to predict the influence of operating temperature on cyclone performance, an experimental investigation on particle separation was conducted in a 300 m
A constitutive model of quasi-Newtonian fluid based on the type of flow is used in abrupt planar contraction flow.The numerical results from finite element anal
The author studies minimal surfaces in 3-dimensional solvable Lie groups with left invariantRiemannian metrics. A Weierstraβ type integral representation formu
The polymerization of amphiphilic self-assemblies is a promising method to synthesize nano-structured materials with novel properties. These materials have many