Search

It is known that the majority of the human genome consists of duplicated sequences. Furthermore, it is believed that a significant part of the rest of the genome also originated from duplicated sequences and has mutated to its current form. In this paper, we investigate the possibility of constructing an exponentially large number of sequences from a short initial sequence using simple duplication rules, including those resembling genomic-duplication processes. In other words, our goal is to find the capacity, or the expressive power, of these string-duplication systems. Our results include exact capacities, and bounds on the capacities, of four fundamental string-duplication systems. The study of these fundamental biologically inspired systems is an important step toward modeling and analyzing more complex biological processes. [ABSTRACT FROM AUTHOR]

We consider rank modulation codes for flash memories that allow for handling arbitrary charge-drop errors. Unlike classical rank modulation codes used for correcting errors that manifest themselves as swaps of two adjacently ranked elements, the proposed translocation rank codes account for more general forms of errors that arise in storage systems. Translocations represent a natural extension of the notion of adjacent transpositions and as such may be analyzed using related concepts in combinatorics and rank modulation coding. Our results include derivation of the asymptotic capacity of translocation rank codes, construction techniques for asymptotically good codes, as well as simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes for permutations, and permutation codes in the Hamming distance. [ABSTRACT FROM PUBLISHER]

The problem of finding a minimum decomposition of a permutation in terms of transpositions with predetermined non-uniform and non-negative costs is addressed. Alternatively, computing the transposition distance between two permutations, where transpositions are endowed with arbitrary non-negative costs, is studied. For such cost functions, polynomial-time, constant-approximation decomposition algorithms are described. For metric-path costs, exact polynomial-time decomposition algorithms are presented. The algorithms in this paper represent a combination of Viterbi-type algorithms and graph-search techniques for minimizing the cost of individual transpositions, and dynamic programing algorithms for finding minimum cost decompositions of cycles. The presented algorithms have a myriad of applications in information theory, bioinformatics, and algebra. [ABSTRACT FROM PUBLISHER]

The "Japanese" theorem is extended to multiple multicast sessions in an arbitrary network to characterize the routing capacity region by the intersection of an infinite collection of half-spaces. An elimination technique is developed to simplify this infinite description into a finite one based upon the shortest routing paths and trees in the network graph. This result is used as a step in providing the capacity regions for two multimessage multicast problems on undirected ring networks; in the first case only unicast and broadcast sessions are considered, and in the second case multicast sessions where the source and destination vertices form lines of adjacent vertices are studied. Network coding is generally necessary to achieve network capacity, but for our multimessage multicast problems, new arguments are used to demonstrate that routing can achieve network coding bounds. [ABSTRACT FROM AUTHOR]