Search

Sorting a permutation by reversals is a famous problem in genome rearrangements. Since 1997, quite some biological evidence were found that in many genomes the reversed regions are usually flanked by a pair of inverted repeats. This type of reversals are called symmetric reversals, which, unfortunately, were largely ignored until recently. In this paper, we investigate the problem of sorting by symmetric reversals, which requires a series of symmetric reversals to transform one chromosome $A$ into the another chromosome $B$. The decision problem of sorting by symmetric reversals is referred to as {\em SSR} (when the input chromosomes $A$ and $B$ are given, we use {\em SSR(A,B)}) and the corresponding optimization version (i.e., when the answer for {\em SSR(A,B)} is yes, using the minimum number of symmetric reversals to convert $A$ to $B$), is referred to as {\em SMSR(A,B)}. The main results of this paper are summarized as follows, where the input is a pair of chromosomes $A$ and $B$ with $n$ repeats. (1) We present an $O(n^2)$ time algorithm to solve the decision problem {\em SSR(A,B)}, i.e., determine whether a chromosome $A$ can be transformed into $B$ by a series of symmetric reversals. (2) We design an $O(n^2)$ time algorithm for a special 2-balanced case of {\em SMSR(A,B)}, where chromosomes $A$ and $B$ both have duplication number 2 and every repeat appears twice in different orientations in $A$ and $B$. (3) We show that SMSR is NP-hard even if the duplication number of the input chromosomes are at most 2, hence showing that the above positive optimization result is the best possible. As a by-product, we show that the \emph{minimum Steiner tree} problem on \emph{circle graphs} is NP-hard, settling the complexity status of a 38-year old open problem., Comment: 35 pages, 12 figures

Knowledge gained through X-ray crystallography fostered structural determination of materials and greatly facilitated the development of modern science and technology in the past century. Atomic details of sample structures is achievable by X-ray crystallography, however, it is only applied to crystalline structures. Imaging techniques based on X-ray coherent diffraction or zone plates are capable of resolving the internal structure of non-crystalline materials at nanoscales, but it is still a challenge to achieve atomic resolution. Here we demonstrate a novel lensless Fourier-transform ghost imaging method with pseudo-thermal hard X-rays by measuring the second-order intensity correlation function of the light. We show that high resolution Fourier-transform diffraction pattern of a complex amplitude sample can be achieved at Fresnel region and the amplitude and phase distributions of a sample in spatial domain can be retrieved successfully. The method of lensless X-ray Fourier-transform ghost imaging extends X-ray crystallography to non-crystalline samples, and its spatial resolution is limited only by the wavelength of the X-ray, thus atomic resolution should be routinely obtainable. Since highly coherent X-ray source is not required, comparing to conventional X-ray coherent diffraction imaging, the method can be implemented with laboratory X-ray sources, and it also provides a potential solution for lensless diffraction imaging with fermions, such as neutron and electron where the intensive coherent source usually is not available., Comment: 9 pages, 4 figures, typos fixed, author affiliations added

This paper focuses on finding a spanning tree of a graph to maximize the number of its internal vertices. We present an approximation algorithm for this problem which can achieve a performance ratio $\frac{4}{3}$ on undirected simple graphs. This improves upon the best known approximation algorithm with performance ratio $\frac{5}{3}$ before. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree, which reveals that a spanning tree of an undirected simple graph has less internal vertices than the edges a maximum path-cycle cover of that graph has. We can also give an example to show that the performance ratio $\frac{4}{3}$ is actually tight for this algorithm. To decide how difficult it is for this problem to be approximated, we show that finding a spanning tree of an undirected simple graph to maximize its internal vertices is Max-SNP-Hard., Comment: 15 pages, 1 figure

Computability logic (CoL) is a formal theory of interactive computation. It understands computational problems as games played by two players: a machine and its environment, uses logical formalism to describe valid principles of computability and formulas to represent computational problems. Logic CL1 is a deductive system for a fragment of CoL. The logical vocabulary contains all of the operators of classical logic and choice operators, the atoms represent elementary games i.e. predicates of classical logic. In this paper, we present a program that takes a CL1-proof of an arbitrary formula $F$, and extract a winning strategy for $F$ from that proof then play $F$ using that strategy. We hope this paper would provide a starting point for further work in program extraction of the CoL-based arithmetic and other CoL-based applied systems., Comment: 1 figure

We introduce a new, substantially simplified version of the toggling-branching recurrence operation of Computability Logic, prove its equivalence to Japaridze's old, "canonical" version, and also prove that both versions preserve the static property of their arguments.

The convention for selecting starting points (that is, initial items) on a computerized adaptive test (CAT) is to choose as starting points items of medium difficulty for all examinees. Selecting a starting point based on prior information about an individual's ability was first suggested many years ago, but has been believed unimportant provided that the CAT is reasonably long. However, starting with a medium difficulty item for all examinees has two potential disadvantages: unnecessary uses of the first one or two items and overuse or overexposure of the items around the medium difficulty. This study analyzed simulated CAT results and suggests significant benefits from administering the first CAT item at a difficulty level suitable to each examinee. Such an adjustment can reduce the use of items around the medium difficulty in the item pool, providing extra help in controlling the exposure rate of the items beyond what standard exposure control methods can achieve. The effect of selecting examinee-appropriate starting points can vary depending on the quality of the information used about examinees' ability levels and the test termination rules applied. (Contains 3 tables, 26 figures, and 8 references.) (Author)

This study attempted to control differences in achievement when examining omitting tendencies of examinees. Test data of randomly sampled examinees (7 samples of 2,000 examinees each) from one national administration of the ACT Assessment were used. The number of responses omitted per examinee was examined over all examinees and over only those who omitted responses. The relationship between test scores and number of omits was negative and weak. More examinees at lower levels omitted responses (and more of them), but some at higher levels also omitted a surprising number of responses. No significant differences in tendencies to omit were found between males and females. Statistically significant differences in the tendency to omit were found among examinees of different ethnic groups, especially between African origin and Caucasian origin samples and between Hispanic origin and Caucasian origin examples, but the differences were all less than one omit on average on the mathematics test. Controlling for potential achievement level differences between ethnic groups by using covariates resulted in only a minimal reduction in omitting tendencies between the groups, suggesting that this is not the explanation for differences between ethnic groups. Ten tables summarize study findings. (Contains 22 references.) (SLD)