检索结果-内蒙古大学图书馆

sparse dynamic programming for evolutionary-tree comparison

SIAM JOURNAL ON COMPUTING 1997年第1期26卷 210-230页

作者： Farach, M Thorup, M UNIV COPENHAGEN DEPT COMP SCIDK-2100 COPENHAGENDENMARK

Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in use. Current practice dictates that trees be constructed using different methods and that the resulting trees should be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study one formalization of the problem: the maximum agreement-subtree (MAST) problem. The MAST problem is as follows: given a set A and two rooted trees T-0 and T-1 leaf-labeled by the elements of A, find a maximum-cardinality subset B of A such that the topological restrictions of T-0 and T-1 to B are isomorphic. In this paper, we will show that this problem reduces to unary weighted bipartite matching (UWBM) with an O(n(1+o(1))) additive overhead. We also show that UWBM reduces linearly to MAST. Thus our algorithm is optimal unless UWBM can be solved in near linear time. The overall running time of our algorithm is O(n(1.5)log n), improving on the previous best algorithm, which runs in O(n(2)). We also derive an O(nc(root log n))-time algorithm for the case of bounded degrees, whereas the previously best algorithm runs in O(n(2)), as in the unbounded case.

关键词： sparse dynamic programming computational biology evolutionary trees

来源：评论

学校读者我要写书评

暂无评论

New tabulation and sparse dynamic programming based techniques for sequence similarity problems

引用

DISCRETE APPLIED MATHEMATICS 2016年第0期212卷 96-103页

作者： Grabowski, Szymon Lodz Univ Technol Inst Appl Comp Sci Al Politech 11 PL-90924 Lodz Poland

Calculating the length l of a longest common subsequence (LCS) of two strings, A of length n and B of length m, is a classic research topic, with many known worst-case oriented results. We present three algorithms for LCS length calculation with respectively O(mn 1g 1g n/ lg(2) n), O(mn/ lg(2) n + r) and O(n + r) time complexity, where the second one works for r = o(mn/(lg n lg lg n)), and the third one for r = Theta(mn/ lg(k) n), for a real constant 1 <= k <= 3, and l = O(n/(lg(k-1) n(lg lg n)(2))), where r is the number of matches in the dynamic programming matrix. We also describe conditions for a given problem sufficient to apply our techniques, with several concrete examples presented, namely the edit distance, the longest common transposition-invariant subsequence (LCTS) and the merged longest common subsequence (MerLCS) problems. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Sequence similarity Longest common subsequence sparse dynamic programming Tabulation

来源：评论

学校读者我要写书评

暂无评论

New tabulation and sparse dynamic programming based techniques for sequence similarity problems 18

New tabulation and sparse dynamic programming based techniqu...

引用

18th Prague Stringology Conference, PSC 2014

作者： Grabowski, Szymon Lodz University of Technology Institute of Applied Computer Science Al. Politechniki 11 Lódź90-924 Poland

ISBN: (纸本)9788001055472

Calculating the length of a longest common subsequence (LCS) of two strings, A of length n and B of length m, is a classic research topic, with many worstcase oriented results known. We present two algorithms for LCS length calculation with respectively O(mn log log n/ log2 n) and O(mn/ log2 n + r) time complexity, the latter working for r = o(mn/(log n log log n)), where r is the number of matches in the dynamic programming matrix. We also describe conditions for a given problem sufficient to apply our techniques, with several concrete examples presented, namely the edit distance, LCTS and MerLCS problems. © Czech Technical University in Prague, Czech Republic.

关键词： Longest common subsequence Sequence similarity sparse dynamic programming Tabulation

来源：评论

学校读者我要写书评

暂无评论

The longest common subsequence problem for small alphabets in the word RAM model

引用

INFORMATION PROCESSING LETTERS 2025年 190卷

作者： Campos, Rodrigo Alexander Castro Univ Autonoma Metropolitana Dept Sistemas San Pablo 420 Mexico City 02200 Mexico

Given two strings of lengths m and n, with m <= n, the longest common subsequence problem consists of computing a common subsequence of maximum length by deleting symbols from both strings. While the O(mn) algorithm devised in 1974 is optimal in the most general setting, algorithms that depend on parameters other than m and n have been proposed since then. In the word RAM model, let w be the word size, s be the alphabet size, d be the number of dominant symbol matches between the strings, and p be the length of the longest common subsequence. Fast algorithms for this problem have complexities O(mn/ log n), O(mn/w), O(ns + min(p(n - p), pm)), O(n logs + d log log min(d, mn/d)), O(ns+min(ds, pm)), and O(ns+s!2s+d logs). In this work, we present an O(n(s+log & lowast;n)+ min(d logs, pm)) algorithm when s is an element of O(w), and also an O(n(s + log & lowast;n) + d) algorithm when s <= w which uses bitwise instructions that became recently available in modern processors.

关键词： Longest common subsequence Small alphabet Word RAM model sparse dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Transposition invariant string matching

引用

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC 2005年第2期56卷 124-153页

作者： Mäkinen, V Navarro, G Ukkonen, E Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Univ Chile Dept Comp Sci Ctr Web Res Santiago Chile

Given strings A = a(1)a(2)...a(m) and B=b(1)b(2)...b(n) over an alphabet Sigma subset of U, where U is some numerical universe closed under addition and subtraction, and a distance function d(A, B) that gives the score of the best (partial) matching of A and B, the transposition invariant distance is min(t is an element of U){d(A + t, B)}, where A + t = (a(1) + t)(a(2) + t)...(a(m) + t). We study the problem of computing the transposition invariant distance for various distance (and similarity) functions d, including Hamming distance, longest common subsequence (LCS), Levenshtein distance, and their versions where the exact matching condition is replaced by an approximate one. For all these problems we give algorithms whose time complexities are close to the known upper bounds without transposition invariance, and for some we achieve these upper bounds. In particular, we show how sparse dynamic programming can be used to solve transposition invariant problems, and its connection with multidimensional range-minimum search. As a byproduct, we give improved sparse dynamic programming algorithms to compute LCS and Levenshtein distance. (c) 2004 Elsevier Inc. All rights reserved.

关键词： edit distance music sequence comparison transposition invariance sparse dynamic programming range-minimum searching

来源：评论

学校读者我要写书评

暂无评论

Efficient computation of gapped substring kernels on large alphabets

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2005年第9期6卷 1323-1344页

作者： Rousu, J Shawe-Taylor, J Univ London Royal Holloway & Bedford New Coll Dept Comp Sci Egham TW20 0EX Surrey England Univ Southampton Sch Elect & Comp Sci Southampton SO17 1BJ Hants England

We present a sparse dynamic programming algorithm that, given two strings s and t, a gap penalty l, and an integer p, computes the value of the gap-weighted length-p subsequences kernel. The algorithm works in time O(p vertical bar M vertical bar log vertical bar t vertical bar), where M = {(i,j)vertical bar s(i) = t(j)} is the set of matches of characters in the two sequences. The algorithm is easily adapted to handle bounded length subsequences and different gap-penalty schemes, including penalizing by the total length of gaps and the number of gaps as well as incorporating character-specific match/gap penalties. The new algorithm is empirically evaluated against a full dynamic programming approach and a trie-based algorithm both on synthetic and newswire article data. Based on the experiments, the full dynamic programming approach is the fastest on short strings, and on long strings if the alphabet is small. On large alphabets, the new sparse dynamic programming algorithm is the most efficient. On medium-sized alphabets the trie-based approach is best if the maximum number of allowed gaps is strongly restricted.

关键词： kernel methods string kernels text categorization sparse dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for computing tree LCS

引用

THEORETICAL COMPUTER SCIENCE 2009年第43期410卷 4303-4314页

作者： Mozes, Shay Tsur, Dekel Weimann, Oren Ziv-Ukelson, Michal Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Brown Univ Providence RI 02912 USA MIT Cambridge MA 02139 USA

The LCS of two rooted, ordered, and labeled trees F and G is the largest forest that can be obtained from both trees by deleting nodes. We present algorithms for computing tree LCS which exploit the sparsity inherent to the tree LCS problem. Assuming G is smaller than F, our first algorithm runs in time O(r . height(F) . height(G) . lg lg vertical bar G vertical bar), where r is the number of pairs (upsilon is an element of F, omega is an element of G) such that upsilon and omega) have the same label. Our second algorithm runs in time O(Lr lg r . lg lg vertical bar G vertical bar), where L is the size of the LCS of F and G. For this algorithm we present a novel three-dimensional alignment graph. Our third algorithm is intended for the constrained variant of the problem in which only nodes with zero or one children can be deleted. For this case we obtain an O(rh lg lg vertical bar G vertical bar) time algorithm, where h = height(F) + height(G). (C) 2009 Elsevier B.V. All rights reserved.

关键词： Tree LCS Tree edit distance Ordered trees Largest common subforest sparse dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Peak alignment using restricted edit distances

引用

BIOMOLECULAR ENGINEERING 2007年第3期24卷 337-342页

作者： Makinen, Veli Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland

A peak is a pair of real values (x, y), where x is the time when peak of height y is registered. In the peak alignment problem, we are given two sequences of peaks, and our task is to align the sequences allowing some basic edit operations on the peaks. We study an instance of the peak alignment problem that arises in the analysis of Mass Spectrometry data in Systems Biology. There the measurement technique guarantees that two peaks (x, y), (x', y') can only be considered the same if x is close enough toe, and y is close enough to y'. We review some methods to do alignment under such restrictions on matches. (C) 2007 Elsevier B.V. All rights reserved.

关键词： mass spectrometry gel electrophoresis peak alignment edit distance sparse dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for the longest common subsequence in k-length substrings

引用

INFORMATION PROCESSING LETTERS 2014年第11期114卷 634-638页

作者： Deorowicz, Sebastian Grabowski, Szymon Silesian Tech Univ Inst Informat PL-44100 Gliwice Poland Lodz Univ Technol Inst Appl Comp Sci PL-90924 Lodz Poland

Finding the longest common subsequence in k-length substrings (LCSk) is a recently proposed problem motivated by computational biology. This is a generalization of the well-known LCS problem in which matching symbols from two sequences A and B are replaced with matching non-overlapping substrings of length k from A and B. We propose several algorithms for LCSk, being non-trivial incarnations of the major concepts known from LCS research (dynamic programming, sparse dynamic programming, tabulation). Our algorithms make use of a linear-time and linear-space preprocessing finding the occurrences of all the substrings of length k from one sequence in the other sequence. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Algorithms Combinatorial problems LCSk sparse dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance

引用

INFORMATION RETRIEVAL 2008年第4期11卷 335-357页

作者： Fredriksson, Kimmo Grabowski, Szymon Univ Kuopio Dept Comp Sci FIN-70211 Kuopio Finland Tech Univ Lodz Dept Comp Engn PL-90924 Lodz Poland

We develop efficient dynamic programming algorithms for pattern matching with general gaps and character classes. We consider patterns of the form p(0) g(a(0),b(0))p(1)g(a(1),b(1)) ... p(m-1), where p(i) subset of Sigma, Sigma is some finite alphabet, and g(a(i) ,b(i)) denotes a gap of length a(i) ...b(i) between symbols p(i) and p(i+1). The text symbol t(j) matches p(i) iff t(j) is an element of p(i) . Moreover, we require that if p(i) matches t(j) , then p(i+1) should match one of the text symbols t(j+ai+1) ... t(j+bi+1). Either or both of a(i) and b (i) can be negative. We also consider transposition invariant matching, i.e., the matching condition becomes t(j) is an element of p(i) + tau, for some constant tau determined by the algorithms. We give algorithms that have efficient average and worst case running times. The algorithms have important applications in music information retrieval and computational biology. We give experimental results showing that the algorithms work well in practice.

关键词： string matching sparse dynamic programming bounded length gaps character classes transposition invariance

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：