A binary string transmitted via a memoryless i.i.d. deletion channel is received as a subsequence of the original input. From this, one obtains a posterior distribution on the channel input, corresponding to a set of candidate supersequences weighted by the number of times the received subsequence can be embedded in them. In a previous work it is conjectured on the basis of experimental data that the entropy of the posterior is minimized and maximized by the constant and the alternating strings, respectively. In this work, we present an algorithm for counting the number of subsequence embeddings using a run-length encoding of strings. We then describe two different ways of clustering the space of supersequences and prove that their cardinality depends only on the length of the received subsequence and its Hamming weight, but not its exact form. Then, we consider supersequences that contain a single embedding of a fixed subsequence, referred to as singletons, and provide a closed form expression for enumerating them using the same run-length encoding. We prove an analogous result for the minimization and maximization of the number of singletons, by the alternating and the uniform strings, respectively. Next, we prove the original minimal entropy conjecture for the special cases of single and double deletions using similar clustering techniques and the same run-length encoding, which allow us to characterize the distribution of the number of subsequence embeddings in the space of compatible supersequences to demonstrate the effect of an entropy decreasing operation.
In coding theory, and more specifically in the context of insertion and deletions channels, similar long-standing problems have been studied extensively, and yet many problems still remain elusive. This includes designing optimal coding schemes and determining the capacity of deletion channels, both of which incorporate the same underlying combinatorial problem addressed in the present work. Considering a finite number of insertions and deletions for designing correcting codes for synchronization errors @cite_16 @cite_1 @cite_17 and reconstructing the original string from a fixed subsequence @cite_8 represent two specific and related research areas. More recent work on the characterization of the number of subsequences obtained via the deletion channel @cite_2 @cite_18 @cite_10 , e.g., in terms of the number of runs in a string, shows great overlap with our work. A graph-theoretic approach for deletion correcting codes, closely related to our clustering analysis, including an alternative proof for the Hamming weight clustering given in Theorem based on a different approach, is given in @cite_14 .
@cite_18 @cite_14 @cite_8 @cite_1 @cite_2 @cite_16 @cite_10 @cite_17
1667855763 2091876558 2098116409 2137484241 2150830972 2003920341 2170857855 2034381439
Although the insertion deletion problem has been studied for more than fifty years, many results still remain elusive. The goal of this work is to present three novel theorems with a combinatorial flavor that shed further light on the structure and nature of insertions deletions. In particular, we give an exact result for the maximum number of common supersequences between two sequences, extending older work by Levenshtein. We then generalize this result for sequences that have different lengths. Finally, we compute the exact neighborhood size for the binary circular (alternating) string C n = 0101 … 01. In addition to furthering our understanding of the insertion deletion channel, these theorems can be used as building blocks in other applications. One such application is developing improved lower bounds on the sizes of insertion deletion-correcting codes. This paper studies problems in data reconstruction, an important area with numerous applications. In particular, we examine the reconstruction of binary and nonbinary sequences from synchronization (insertion deletion-correcting) codes. These sequences have been corrupted by a fixed number of symbol insertions (larger than the minimum edit distance of the code), yielding a number of distinct traces to be used for reconstruction. We wish to know the minimum number of traces needed for exact reconstruction. This is a general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding an upper bound on the number of distinct traces necessary to guarantee exact reconstruction. Without specific knowledge of the code words, this upper bound is tight. We apply our results to the famous single deletion insertion-correcting Varshamov–Tenengolts (VT) codes and show that a significant number of VT code word pairs achieve the worst case number of outputs needed for exact reconstruction. We also consider extensions to other channels, such as adversarial deletion and insertion deletion channels and probabilistic channels. We study the problem of synchronization of two remotely located data sources, which are mis-synchronized due to deletions and insertions. This is an important problem since a small number of synchronization errors can induce a large Hamming distance between the two sources. The goal is to effect synchronization with the rate-efficient use of lossless bidirectional links between the two sources. In this work, we focus on the following model. A binary sequence X of length n is edited to generate the sequence at the remote end, say Y, where the editing involves random deletions and insertions, possibly in small bursts. The problem is to synchronize Y with X with minimal exchange of information (in terms of both the average communication rate and the average number of interactive rounds of communication). We focus here on the case where the number of edits is much smaller than n, and propose an interactive algorithm which is computationally simple and has near-optimal communication complexity. Our algorithm works by efficiently splitting the source sequence into pieces containing either just a single deletion insertion or a single burst deletion insertion. Each of these pieces is then synchronized using an optimal one-way synchronization code, based on the single-deletion correcting channel codes of Varshamov and Tenengolts (VT codes). We consider deletion correcting codes over a (q ) -ary alphabet. It is well known that any code capable of correcting (s ) deletions can also correct any combination of (s ) total insertions and deletions. To obtain asymptotic upper bounds on code size, we apply a packing argument to channels that perform different mixtures of insertions and deletions. Even though the set of codes is identical for all of these channels, the bounds that we obtain vary. Prior to this paper, only the bounds corresponding to the all-insertion case and the all-deletion case were known. We recover these as special cases. The bound from the all-deletion case, due to Levenshtein, has been the best known for more than 45 years. Our generalized bound is better than Levenshtein's bound whenever the number of deletions to be corrected is larger than the alphabet size. We take a graph theoretic view of deletion correcting codes. The problem of finding an n-bit s-deletion correcting code is equivalent to finding an independent set in a particular graph. We discuss the relationship between codes and colorings and demonstrate that the VT codes are optimal in a coloring sense. We describe a method of partitioning the set of bit strings by Hamming weight and finding codes within each partition. In the single deletion case, we find an optimal coloring of the constant Hamming weight induced subgraphs. We show that the resulting code is asymptotically optimal. We also prove a lower bound on size of codes constructed using these partitions for any number of deletions. In a document network such as a citation network of scientific documents, web-logs, etc., the content produced by authors exhibits their interest in certain topics. In addition some authors influence other authors' interests. In this work, we propose to model the influence of cited authors along with the interests of citing authors. Moreover, we hypothesize that apart from the citations present in documents, the context surrounding the citation mention provides extra topical information about the cited authors. However, associating terms in the context to the cited authors remains an open problem. We propose novel document generation schemes that incorporate the context while simultaneously modeling the interests of citing authors and influence of the cited authors. Our experiments show significant improvements over baseline models for various evaluation criteria such as link prediction between document and cited author, and quantitatively explaining unseen text. Motivated by the study of deletion channels, this paper presents improved bounds on the number of subsequences obtained from a binary string @math of length @math under @math deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string @math ; where a run is a maximal substring of the same character. Our improved bounds are obtained by a structural analysis of the family of @math -run strings @math , an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every @math , we present @math -run strings with the minimum (respectively maximum) number of subsequences under any @math deletions; we perform an exact analysis of the number of subsequences of these extremal strings; and show that this number can be calculated in polynomial time. The sequence reconstruction problem , first proposed by Levenshtein, models the setup in which a sequence from some set is transmitted over several channels, and the decoder receives the outputs from every channel. The channels are almost independent as it is only required that all outputs are different from each other. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius @math , where the distance between their centers is at least @math . The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendall-tau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted sequence can be arbitrary, we study the setup, where the transmitted sequence belongs to a single-deletion-correcting code and there are @math deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder. We study memoryless channels with synchronization errors as defined by a stochastic channel matrix allowing for symbol drop-outs or symbol insertions with particular emphasis on the binary and non-binary deletion channels. We offer a different look at these channels by considering equivalent models by fragmenting the input sequence where different subsequences travel through different channels. The resulting output symbols are combined appropriately to come up with an equivalent input-output representation of the original channel which allows for derivation of new upper bounds on the channel capacity. We consider both random and deterministic types of fragmentation processes applied to binary and nonbinary deletion channels. With two specific applications of this idea, a random fragmentation applied to a binary deletion channel and a deterministic fragmentation process applied to a nonbinary deletion channel, we prove certain inequality relations among the capacities of the original channels and those of the introduced subchannels. The resulting inequalities prove useful in deriving tighter capacity upper bounds for: 1) independent identically distributed (i.i.d.) deletion channels when the deletion probability exceeds 0.65 and 2) nonbinary deletion channels. Some extensions of these results, for instance, to the case of deletion substitution channels are also explored. The binary deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Input bits are deleted independently with probability d, and when they are not deleted, they are not affected by the channel. Despite significant effort, little is known about the capacity of this channel and even less about optimal coding schemes. In this paper, we develop a new systematic approach to this problem, by demonstrating that capacity can be computed in a series expansion for small deletion probability. We compute three leading terms of this expansion, and find an input distribution that achieves capacity up to this order. This constitutes the first optimal random coding result for the deletion channel. The key idea employed is the following: We understand perfectly the deletion channel with deletion probability d=0. It has capacity 1 and the optimal input distribution is iid Bernoulli (1 2). It is natural to expect that the channel with small deletion probabilities has a capacity that varies smoothly with d, and that the optimal input distribution is obtained by smoothly perturbing the iid Bernoulli (1 2) process. Our results show that this is indeed the case. A citing sentence is one that appears in a scientific article and cites previous work. Citing sentences have been studied and used in many applications. For example, they have been used in scientific paper summarization, automatic survey generation, paraphrase identification, and citation function classification. Citing sentences that cite multiple papers are common in scientific writing. This observation should be taken into consideration when using citing sentences in applications. For instance, when a citing sentence is used in a summary of a scientific paper, only the fragments of the sentence that are relevant to the summarized paper should be included in the summary. In this paper, we present and compare three different approaches for identifying the fragments of a citing sentence that are related to a given target reference. Our methods are: word classification, sequence labeling, and segment classification. Our experiments show that segment classification achieves the best results. By using a run-length representation of sequences, ways to determine suband supersequences are discussed. This is then used in determining the number of sub- and supersequences of a sequence after double insertions or deletions. It is also used in creating subsequence supersequence books that are searched to find new double insertion deletion correcting code books with higher cardinalities than those already known. We develop several analytical lower bounds on the capacity of binary insertion and deletion channels by considering independent uniformly distributed (i.u.d.) inputs and computing lower bounds on the mutual information between the input and output sequences. For the deletion channel, we consider two different models: i.i.d. deletion-substitution channel and i.i.d. deletion channel with additive white Gaussian noise (AWGN). These two models are considered to incorporate effects of the channel noise along with the synchronization errors. For the insertion channel case, we consider Gallager's model in which the transmitted bits are replaced with two random bits and uniform over the four possibilities independently of any other insertion events. The general approach taken is similar in all cases, however the specific computations differ. Furthermore, the approach yields a useful lower bound on the capacity for a wide range of deletion probabilities of the deletion channels, while it provides a beneficial bound only for small insertion probabilities (less than 0.25) of the insertion model adopted. We emphasize the importance of these results by noting that: 1) our results are the first analytical bounds on the capacity of deletion-AWGN channels, 2) the results developed are the best available analytical lower bounds on the deletion-substitution case, 3) for the Gallager insertion channel model, the new lower bound improves the existing results for small insertion probabilities. We study the problem of synchronizing two files X and Y at two distant nodes A and B that are connected through a two-way communication channel. We assume that file Y at node B is obtained from file X at node A by inserting and deleting a small fraction of symbols in X. More specifically, we consider the case where X is a non-binary non-uniform string, and deletions and insertions happen uniformly with rates βd and βi, respectively. We propose a synchronization protocol between node A and node B that needs to transmit O(q H2(βd+βi)n log 1 βd+βi) bits (where n is the length of X, q is the alphabet size and H2 is the collision entropy of X) and reconstructs X at node B with error probability exponentially low in n. This protocol readily generalizes the recent result by Tabatabaei Yazdi and Dolecek that dealt with synchronization from binary uniform source and under only deletion errors. Synchronization channels, which can remove codeword symbols or introduce extraneous symbols, pose additional difficulties when compared to the commonly-studied substitution channel. A traditional problem in this area is to count the number of sequences formed when deleting a fixed number of symbols from a sequence. This work contains our first effort towards solving a similar, yet previously unexplored, problem: deriving bounds on the number of sequences obtained by deleting and inserting a fixed number of symbols. This paper considers a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability d, or an extra bit is added after it with probability i, or it is transmitted unmodified with probability 1-d-i. A computable lower bound on the capacity of this channel is derived. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter longer, some runs get deleted, and some new runs are added. It is difficult for the decoder to synchronize the channel output sequence to the transmitted codeword mainly due to deleted runs and new inserted runs. The main idea is a mutual information decomposition in terms of the rate achieved by a suboptimal decoder that determines the positions of the deleted and inserted runs in addition to decoding the transmitted codeword. The mutual information between the channel input and output sequences is expressed as the sum of the rate achieved by this decoder and the rate loss due to its suboptimality. Obtaining computable lower bounds on each of these quantities yields a lower bound on the capacity. The bounds proposed in this paper provide the first characterization of achievable rates for channels with general insertions, and for channels with both deletions and insertions. For the special case of the deletion channel, the proposed bound improves on the previous best lower bound for deletion probabilities up to 0.3. A subsequence is obtained from a string by deleting any number of characters; thus in contrast to a substring, a subsequence is not necessarily a contiguous part of the string. Counting subsequences under various constraints has become relevant to biological sequence analysis, to machine learning, to coding theory, to the analysis of categorical time series in the social sciences, and to the theory of word complexity. We present theorems that lead to efficient dynamic programming algorithms to count (1) distinct subsequences in a string, (2) distinct common subsequences of two strings, (3) matching joint embeddings in two strings, (4) distinct subsequences with a given minimum span, and (5) sequences generated by a string allowing characters to come in runs of a length that is bounded from above. Purpose – The purpose of this paper is to suggest an alternative to the widely used Times Cited criterion for analysing citation networks. The approach involves taking account of the natures of the papers that cite a given paper, so as to differentiate between papers that attract the same number of citations.Design methodology approach – ArticleRank is an algorithm that has been derived from Google's PageRank algorithm to measure the influence of journal articles. ArticleRank is applied to two datasets – a citation network based on an early paper on webometrics, and a self‐citation network based on the 19 most cited papers in the Journal of Documentation – using citation data taken from the Web of Knowledge database.Findings – ArticleRank values provide a different ranking of a set of papers from that provided by the corresponding Times Cited values, and overcomes the inability of the latter to differentiate between papers with the same numbers of citations. The difference in rankings between Times Cited ... Scholars are increasingly citing electronic “web references” which are not preserved in libraries or full text archives. WebCite is a new standard for citing web references. To “webcite” a document involves archiving the cited Web page through www.webcitation.org and citing the WebCite permalink instead of (or in addition to) the unstable live Web page. This journal has amended its “instructions for authors” accordingly, asking authors to archive cited Web pages before submitting a manuscript. Almost 200 other journals are already using the system. We discuss the rationale for WebCite, its technology, and how scholars, editors, and publishers can benefit from the service. Citing scholars initiate an archiving process of all cited Web references, ideally before they submit a manuscript. Authors of online documents and websites which are expected to be cited by others can ensure that their work is permanently available by creating an archived copy using WebCite and providing the citation information including the WebCite link on their Web document(s). Editors should ask their authors to cache all cited Web addresses (Uniform Resource Locators, or URLs) “prospectively” before submitting their manuscripts to their journal. Editors and publishers should also instruct their copyeditors to cache cited Web material if the author has not done so already. Finally, WebCite can process publisher submitted “citing articles” (submitted for example as eXtensible Markup Language [XML] documents) to automatically archive all cited Web pages shortly before or on publication. Finally, WebCite can act as a focussed crawler, caching retrospectively references of already published articles. Copyright issues are addressed by honouring respective Internet standards (robot exclusion files, no-cache and no-archive tags). Long-term preservation is ensured by agreements with libraries and digital preservation organizations. The resulting WebCite Index may also have applications for research assessment exercises, being able to measure the impact of Web services and published Web documents through access and Web citation metrics. @PARASPLIT [J Med Internet Res 2005;7(5):e60] A new form of document coupling called co-citation is defined as the frequency with which two documents are cited together. The co-citation frequency of two scientific papers can be determined by comparing lists of citing documents in the Science Citation Index and counting identical entries. Networks of co-cited papers can be generated for specific scientific specialties, and an example is drawn from the literature of particle physics. Co-citation patterns are found to differ significantly from bibliographic coupling patterns, but to agree generally with patterns of direct citation. Clusters of co-cited papers provide a new way to study the specialty structure of science. They may provide a new approach to indexing and to the creation of SDI profiles.