Affordable Access

Publisher Website

Weighted LCS

Authors
Journal
Journal of Discrete Algorithms
1570-8667
Publisher
Elsevier
Publication Date
Volume
8
Issue
3
Identifiers
DOI: 10.1016/j.jda.2010.02.001
Keywords
  • String Algorithms
  • Approximation Algorithms
  • Np-Hard Problem
  • Position Weight Matrix
Disciplines
  • Computer Science

Abstract

Abstract 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 ( z n z + 1 ) . For the second, we consider the log-probability version of the problem, prove NP -hardness and provide an approximation algorithm.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

On the Set LCS and Set-Set LCS Problems

on Journal of Algorithms Jan 01, 1993

Generalized LCS

on Theoretical Computer Science Jan 01, 2008

LCs--remember your roots!

on Journal of human lactation : o... September 1991
More articles like this..