Weighted LCS

作     者：Amir, Amihood Gotthilf, Zvi Shalom, B. Riva 

作者机构：Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA 

出 版 物：《JOURNAL OF DISCRETE ALGORITHMS》 (离散算法杂志)

年 卷 期：2010年第8卷第3期

页      面：273-281页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：ISF [35/05] Binational Israel-Korea 

主　　题：String algorithms Approximation algorithms NP-hard problem Position weight matrix 

摘      要：The Longest Common Subsequence (LCS) of two strings A, B is a well studied problem having a wide range of applications. When each symbol of the input strings is assigned a positive weight the problem becomes the Heaviest Common Subsequence (HCS) problem. In this paper we consider a different version of weighted LCS on Position Weight Matrices (PWM). The Position Weight Matrix was introduced as a tool to handle a set of sequences that are not identical, yet, have many local similarities. Such a weighted sequence is a statistical image of this set where we are given the probability of every symbol s occurrence at every text location. We consider two possible definitions of LCS on PWM. For the first, we solve the LCS problem of z sequences in time O(zn(z+ 1)). For the second, we consider the log-probability version of the problem, prove NP-hardness and provide an approximation algorithm. (C) 2010 Elsevier B.V. All rights reserved.