196,352 research outputs found
Ukkonen\'s tree: combinatorial characterization and applications
No full textA árvore de sufixos é uma estrutura dados, que representa em espaço linear todos os fatores de uma palavra, com diversos exemplos de aplicações práticas. Neste trabalho, definimos uma estrutura mais geral: a árvore de Ukkonen. Provamos para ela diversas propriedades combinatórias, dentre quais, a minimalidade em um sentido preciso. Acreditamos que a apresentação aqui oferecida, além de mais geral que as árvores de sufixo, tem a vantagem de oferecer uma descrição explícita da topologia da árvore, de seus vértices, arestas e rótulos, o que não vimos em nenhum outro trabalho. Como aplicações, apresentamos também a árvore esparsa de sufixos (que armazena apenas um subconjunto dos sufixos) e a árvore de k-fatores (que armazena apenas os segmentos de comprimento k, ao invés dos sufixos) definidas como casos particulares das árvores de Ukkonen. Propomos para as árvores esparsas um novo algoritmo de construção com tempo O(n) e espaço O(m), onde n é tamanho da palavra e m é número de sufixos. Para as árvores de k-fatores, propomos um novo algoritmo online com tempo e espaço O(n), onde n é o tamanho da palavra.The suffix tree is a data structure that represents, in linear space, all factors of a given word, with several examples of practical applications. In this work, we define a more general structure: the Ukkonen\'s tree. We prove many properties for it, among them, its minimality in a precise sense. We believe that this presentation, besides being more general than the suffix trees, has the advantage of offering an explicit description of the tree topology, its vertices, edges and labels, which was not seen in any other work. As applications, we also presents the sparse suffix tree (which stores only a subset of the suffixes) and the k-factor tree (which stores only the substrings of length k, instead of the suffixes), both defined as Ukkonen\'s tree special cases. We propose a new construction algorithm for the sparse suffix trees with time O(n) and space O(m), where n is the size of the word and m is the number of suffixes. For the k-factor trees, we propose a new online algorithm with time and space O(n), where n is the size of the word
Finding significant matches of position weight matrices in linear time
No full textPosition weight matrices are an important method for modeling signals or motifs in biological sequences, both in DNA and protein contexts. In this paper, we present fast algorithms for the problem of finding significant matches of such matrices. Our algorithms are of the online type, and they generalize classical multipattern matching, filtering, and superalphabet techniques of combinatorial string matching to the problem of weight matrix matching. Several variants of the algorithms are developed, including multiple matrix extensions that perform the search for several matrices in one scan through the sequence database. Experimental performance evaluation is provided to compare the new techniques against each other as well as against some other online and index-based algorithms proposed in the literature. Compared to the brute-force O(mn) approach, our solutions can be faster by a factor that is proportional to the matrix length m. Our multiple-matrix filtration algorithm had the best performance in the experiments. On a current PC, this algorithm finds significant matches (p = 0.0001) of the 123 JASPAR matrices in the human genome in about 18 minutes
The BREW workshop series: a stimulating experience in PhD education
No full textGiegerich R, Brazma A, Jonassen I, Ukkonen E, Vingron M. The BREW workshop series: a stimulating experience in PhD education. Briefings in Bioinformatics. 2008;9(3):250-253.Over recent years, five European PhD programmes have organized a series of Bioinformatics Research and Education Workshops. These workshops address the needs of first-year PhD students and have been designed to combine a maximum of educational impact and scientific stimulation with a minimum of financial and administrative effort. We describe the BREW experience and argue that this type of event constitutes an attractive component of PhD education in computational biology and beyond
Longest common substrings with k mismatches
No full textAbstractThe longest common substring with k-mismatches problem is to find, given two strings S1 and S2, a longest substring A1 of S1 and A2 of S2 such that the Hamming distance between A1 and A2 is ≤k. We introduce a practical O(nm) time and O(1) space solution for this problem, where n and m are the lengths of S1 and S2, respectively. This algorithm can also be used to compute the matching statistics with k-mismatches of S1 and S2 in O(nm) time and O(m) space. Moreover, we also present a theoretical solution for the k=1 case which runs in O(nlogm) time, assuming m≤n, and uses O(m) space, improving over the existing O(nm) time and O(m) space bound of Babenko and Starikovskaya [1]
Dr. Duane M. Jackson, Morehouse College, July 2011
No full textThis video is a conversation with Dr. Duane M. Jackson. Dr. Jackson talks about his paper, "Recall and the Serial Position Effect: The Role of Primacy and Recency on Accounting Students' Performance." Jackie Daniel, AUC Woodruff Library, is the interviewer
sj-pdf-1-sjs-10.1177_14574969211049055 – Supplemental material for Trends in acute abdominal pain visits to EDs and rate of abdominal surgeries during the COVID-19 pandemic in Finland: A retrospective register study
No full textSupplemental material, sj-pdf-1-sjs-10.1177_14574969211049055 for Trends in acute abdominal pain visits to EDs and rate of abdominal surgeries during the COVID-19 pandemic in Finland: A retrospective register study by Saara Jäntti, Ville Ponkilainen, Ilari Kuitunen, Teemu P. Hevonkorpi, Juha Paloneva, Mika Ukkonen and Ville M. Mattila in Scandinavian Journal of Surgery</p
"Reflections on the subject of Emigration from Europe with a view to Settlement in the United States" By M. Carey.
No full text"Reflections on the subject of Emigration from Europe with a view to Settlement in the United States: containing bried sketches of the moral and political character of those states.
By M. Carey, member of the American philosophical, and of the American Antiquarian Society, and author of The Olive Branch, Cindiciae Hibernicae, essays on banking, on political economy, and on internal improvement.
To which are now added the English editor's comments on the subject; together with Important Advice to Emigrants, and Cautions Against Impositions Practiced in the Outports
Dispelling the Myths Behind First-author Citation Counts
No full textWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
Dr. Glendon Swarthout
No full textHosted by Roger M. Busfield, MSU Assistant Professor of Speech and Theater, Meet the Author is designed to introduce a general audience to a contemporary author and their work through in-depth interviews. This episode features a conversation between Dr. Glendon Swarthout, prolific author and English professor at MSU, and assistant professors Sam S. Baskett and Theodore B. Strandness
- …
