1,354,954 research outputs found
A survey of BWT variants for string collections
No full textMotivation: In recent years, the focus of bioinformatics research has moved from individual sequences to collections of sequences. Given the fundamental role of the Burrows-Wheeler Transform (BWT) in string processing, a number of dedicated tools have been developed for computing the BWT of string collections. While the focus has been on improving efficiency, both in space and time, the exact definition of the BWT employed has not been at the center of attention. As we show in this paper, the different tools in use often compute non-equivalent BWT variants: the resulting transforms can differ from each other significantly, including the number r of runs, a central parameter of the BWT. Moreover, with many tools, the transform depends on the input order of the collection. In other words, on the same dataset, the same tool may output different transforms if the dataset is given in a different order. Results: We studied 18 dedicated tools for computing the BWT of string collections and were able to identify 6 different BWT variants computed by these tools. We review the differences between these BWT variants, both from a theoretical and from a practical point of view, comparing them on 8 real-life biological datasets with different characteristics. We find that the differences can be extensive, depending on the datasets, and are largest on collections of many similar short sequences. The parameter r, the number of runs of the BWT, also shows notable variation between the different BWT variants; on our datasets, it varied by a multiplicative factor of up to 4.2. Availability: Source code and scripts to replicate the results and download the data used in the article are available at https://github.com/davidecenzato/BWT-variants-for-string-collections. Supplementary information: Supplementary data are available at Bioinformatics online
JUSTINE WATTS, Violin MASTERS RECITAL Wednesday September 21, 1988 8:00 p.m. in the Shepherd School Recital Hall
No full textPlaylist: Concerto in G major, K. 216 / Wolfgang Amadeus Mozart (1756-1791) -- Sonata in A major / César Franck (1822-1890) -- "Gemstone" / David Liptak -- Introduction and rondo capriccioso, op. 28 / Camille Saint-Saëns (1835-1921).This recital is given in partial fulfillment of the requirements for the Master of Music degree
A BWT-based algorithm for random de Bruijn sequence construction
No full textA binary de Bruijn sequence (dB sequence) of order k is a circular binary string that contains each k-length word exactly once as a substring. Most existing algorithms construct a specific dB sequence, or members of a specific class of dB sequences, representing only a tiny frac- tion of the complete set. The only algorithms capable of generating all dB sequences are based on finding Euler cycles in de Bruijn graphs. Here, we present an algorithm for constructing random binary dB sequences which uses the extended Burrows-Wheeler Transform. Our method is simple to implement (less than 120 lines of C++ code) and can produce random dB sequences of any order. Even though it does not output dB sequences uniformly at random, it provably outputs each dB sequence with positive probability. The algorithm runs in linear space and near-linear time in the length of the dB sequence and needs less than one second on a lap- top computer for orders up to 23, including outputting the sequence. It can be straightforwardly extended to any constant-size alphabet. To the best of our knowledge, this is the first practical algorithm for generating random dB sequences which is capable of producing all dB sequences. Apart from its immediate usefulness in contexts where it is desirable to use a dB sequence that cannot be guessed easily, we also demonstrate our algorithm’s potential in theoretical studies, giving hitherto unknown estimates of the average discrepancy of binary dB sequences. The code is availabe (in C++ and python) at https://github.com/lucaparmigiani/ rnd dbseq
A fast and simple algorithm for the Money Changing Problem
No full textThe Money Changing Problem (MCP) can be stated as follows: Given k positive integers a1 <· · · < ak and a query integer M , is there a linear combination i ci ai = M with non-negative integers ci , a decomposition of M? If so, produce one or all such decompositions.The largest integer without such a decomposition is called the Frobenius number g(a1, . . . , ak ). A data structure called the residue table of a1 words can be used to compute the Frobenius number in time O(a1). We present an intriguingly simple algorithm for computing the residue table which runs in time O(ka1), with no additional memory requirements, outperforming the best previously known algorithm. Simulations show that it performs well even on “hard” instances from the literature. In addition, we can employ the residue table to answer MCP decision instances in constant time, and a slight modification of size O(a1) to compute one decomposition for a query M. Note that since both computing the Frobenius number and MCP (decision) are NP-hard, one cannot expect to find an algorithm that is polynomial in the size of the input, i.e., in k,logak, and log M.We then give an algorithm which, using a modification of the residue table, also constructible in O(ka1) time, computes all decompositions of a query integer M. Its worst-case running time is O(ka1) for each decomposition, thus the total runtime depends only on the output size and is independent of the size of query M itself.We apply our latter algorithm to interpreting mass spectrometry (MS) peaks: Due to its high speed and accuracy, MS is now the method of choice in protein identification. Interpreting individual peaks is one of the recurring subproblems in analyzing MS data; the task is to identify sample molecules whose mass the peak possibly represents. This can be stated as an MCP instance, with the masses of the individual amino acids as the k integers a1 , . . . , ak . Our simulations show that our algorithm is fast on real data and is well suited for generating candidates for peak interpretation
On the resemblance between the Kornai-Liptak and cross decomposition techniques for block-angular linear programs
No full textIn this paper the resemblance is demonstrated between the master- and subproblems generated by the Kornai-Liptak algorithm and the subproblems obtained by using the cross decomposition method on linear optimization problems with block-angular structure. The significance of the similarity between these two algorithms becomes apparent considering the main disadvantage attributed to cross decomposition. In cross decomposition a master problem has to be solved from time to time since the subproblems alone do not always give a converging sequence of primal and dual solutions. But if the cross decomposition algorithm is modified in such a way that the successive primal and dual subproblem solutions are taken into consideration with equal weights, this results in the Kornai-Liptak algorithm for which convergence is guaranteed
Words with the Smallest Number of Closed Factors (extended abstract)
No full textA word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences. We show that any word of length n contains at least n+1 closed factors (i.e., factors that are closed words). We investigate the language L of words over the alphabet {a, b} containing exactly n + 1 closed factors. We show that a word belongs to L if and only if its closed factors and its palindromic factors coincide (and therefore the words in L are rich words). We also show that L coincides with the language of conjugates of words in a∗b∗
A Conversation on the Supreme Court With Adam Liptak
No full textJoin the Burns Center for a conversation on the Supreme Court with Adam Liptak, who is considered one of the most highly regarded legal affairs journalists in the country. He will be joined by two distinguished Cardozo law professors, Jessica Roth and Alexander Reinert. They will discuss current ethical issues surrounding the court, challenges to the court\u27s legitimacy and upcoming and recently decided cases on issues such as abortion rights, gun regulations, same sex marriage and more.https://larc.cardozo.yu.edu/event-invitations-2023/1027/thumbnail.jp
When a Dollar in a Fully Clustered Word Makes a BWT
No full textThe Burrows-Wheeler Transform (BWT) is a powerful transform widely used in string compression and string processing. It produces a reversible permutation of the characters of the input string, often allowing for easier compression of the string, while also enabling fast pattern matching. While the BWT is defined for every word, not every word is the BWT of some word. A characterization of BWT images was given in [Likhomanov and Shur, CSR, 2011], based on the standard permutation of the string.
Often an end-of-file character can be inserted to make w the BWT of some string v$. This question was answered in [Giuliani et al. Theor. Comput. Sci. 2021], where an efficient algorithm was presented for computing all such positions (called nice positions), and a characterization of nice positions was given, based on pseudo-cycles in the standard permutation of w.
In this paper, we give a stronger characterization of nice positions: We show that these can be characterized using only essential pseudo-cycles, which constitute a small subset of all possible pseudo-cycles. We present an algorithm to compute all essential pseudo-cycles of a word w.
In the second part of the paper, we study nice positions of fully clustered words: these are words w whose number of runs equals the number of distinct characters occurring in w. Fully clustered words are of particular interest due to their extreme compressibility, and words whose BWT is fully clustered have been studied extensively. We are interested in the number of nice positions of fully clustered words, as well as in the number of fully clustered words with k nice positions, for fixed k and word length
A Conversation on the Supreme Court With Adam Liptak
No full textJoin the Burns Center for a conversation on the Supreme Court with Adam Liptak, who is considered one of the most highly regarded legal affairs journalists in the country. He will be joined by two distinguished Cardozo law professors, Jessica Roth and Alexander Reinert. They will discuss current ethical issues surrounding the court, challenges to the court\u27s legitimacy and upcoming and recently decided cases on issues such as abortion rights, gun regulations, same sex marriage and more.https://larc.cardozo.yu.edu/event-invitations-2023/1027/thumbnail.jp
Broadcasting in Complete Networks with Dynamic Edge Faults
No full textWe investigate the problem of broadcasting in a complete synchronous network with dynamic edge faults. The faults may be loss of messages only (omissions) or of arbitrary type (Byzantine fualts). In both cases, broadcasting can be done in at most 5 rounds, i.e. in constant time, as long as the maximal number \phi of fautls per round allows broadcasting at all. We present algorithms which are optimal for different variants of the problem
- …
