The Experts below are selected from a list of 4242 Experts worldwide ranked by ideXlab platform

B. Riva Shalom - One of the best experts on this subject based on the ideXlab platform.

  • SPIRE - Weighted shortest common supersequence
    String Processing and Information Retrieval, 2011
    Co-Authors: Amihood Amir, Zvi Gotthilf, B. Riva Shalom
    Abstract:

    The Shortest Common Supersequence (SCS) is the problem of seeking a shortest possible sequence that contains each of the input sequences as a subsequence. In this paper we consider applying the problem to 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 SCS on PWM. For the first, we give a polynomial time algorithm, having two input sequences. For the second, we prove NP-hardness.

  • Weighted LCS
    Journal of Discrete Algorithms, 2010
    Co-Authors: Amihood Amir, Zvi Gotthilf, B. Riva Shalom
    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(zn^z^+^1). For the second, we consider the log-probability version of the problem, prove NP-hardness and provide an approximation algorithm.

  • Weighted LCS
    Lecture Notes in Computer Science, 2009
    Co-Authors: Amihood Amir, Zvi Gotthilf, B. Riva Shalom
    Abstract:

    The Longest Common Subsequence (LCS) of two strings A and 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 Weighted LCS problem of z sequences in time O(zn z + 1). For the second, we prove $\cal{NP}$-hardness and provide an approximation algorithm.

Rahul Siddharthan - One of the best experts on this subject based on the ideXlab platform.

  • dinucleotide Weight matrices for predicting transcription factor binding sites generalizing the Position Weight Matrix
    PLOS ONE, 2010
    Co-Authors: Rahul Siddharthan
    Abstract:

    Background Identifying transcription factor binding sites (TFBS) in silico is key in understanding gene regulation. TFBS are string patterns that exhibit some variability, commonly modelled as “Position Weight matrices” (PWMs). Though convenient, the PWM has significant limitations, in particular the assumed independence of Positions within the binding motif; and predictions based on PWMs are usually not very specific to known functional sites. Analysis here on binding sites in yeast suggests that correlation of dinucleotides is not limited to near-neighbours, but can extend over considerable gaps. Methodology/Principal Findings I describe a straightforward generalization of the PWM model, that considers frequencies of dinucleotides instead of individual nucleotides. Unlike previous efforts, this method considers all dinucleotides within an extended binding region, and does not make an attempt to determine a priori the significance of particular dinucleotide correlations. I describe how to use a “dinucleotide Weight Matrix” (DWM) to predict binding sites, dealing in particular with the complication that its entries are not independent probabilities. Benchmarks show, for many factors, a dramatic improvement over PWMs in precision of predicting known targets. In most cases, significant further improvement arises by extending the commonly defined “core motifs” by about 10bp on either side. Though this flanking sequence shows no strong motif at the nucleotide level, the predictive power of the dinucleotide model suggests that the “signature” in DNA sequence of protein-binding affinity extends beyond the core protein-DNA contact region. Conclusion/Significance While computationally more demanding and slower than PWM-based approaches, this dinucleotide method is straightforward, both conceptually and in implementation, and can serve as a basis for future improvements.

Amihood Amir - One of the best experts on this subject based on the ideXlab platform.

  • SPIRE - Weighted shortest common supersequence
    String Processing and Information Retrieval, 2011
    Co-Authors: Amihood Amir, Zvi Gotthilf, B. Riva Shalom
    Abstract:

    The Shortest Common Supersequence (SCS) is the problem of seeking a shortest possible sequence that contains each of the input sequences as a subsequence. In this paper we consider applying the problem to 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 SCS on PWM. For the first, we give a polynomial time algorithm, having two input sequences. For the second, we prove NP-hardness.

  • Weighted LCS
    Journal of Discrete Algorithms, 2010
    Co-Authors: Amihood Amir, Zvi Gotthilf, B. Riva Shalom
    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(zn^z^+^1). For the second, we consider the log-probability version of the problem, prove NP-hardness and provide an approximation algorithm.

  • Weighted LCS
    Lecture Notes in Computer Science, 2009
    Co-Authors: Amihood Amir, Zvi Gotthilf, B. Riva Shalom
    Abstract:

    The Longest Common Subsequence (LCS) of two strings A and 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 Weighted LCS problem of z sequences in time O(zn z + 1). For the second, we prove $\cal{NP}$-hardness and provide an approximation algorithm.

Zuba W. - One of the best experts on this subject based on the ideXlab platform.

  • Weighted Shortest Common Supersequence problem revisited
    'Springer Science and Business Media LLC', 2019
    Co-Authors: Charalampopoulos P., Kociumaka T., Pissis S., Radoszewski J., Rytter W., Straszyński J., Waleń T., Zuba W.
    Abstract:

    A Weighted string, also known as a Position Weight Matrix, is a sequence of probability distributions over some alphabet. We revisit the Weighted Shortest Common Supersequence (WSCS) problem, introduced by Amir et al. [SPIRE 2011], that is, the SCS problem on Weighted strings. In the WSCS problem, we are given two Weighted strings (Formula presented) and (Formula presented) and a threshold (Formula presented) on probability, and we are asked to compute the shortest (standard) string S such that both (Formula presented) and (Formula presented) match subsequences of S (not necessarily the same

Wiktor Zuba - One of the best experts on this subject based on the ideXlab platform.

  • SPIRE - Weighted Shortest Common Supersequence problem revisited
    String Processing and Information Retrieval, 2019
    Co-Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Abstract:

    A Weighted string, also known as a Position Weight Matrix, is a sequence of probability distributions over some alphabet. We revisit the Weighted Shortest Common Supersequence (WSCS) problem, introduced by Amir et al. [SPIRE 2011], that is, the SCS problem on Weighted strings. In the WSCS problem, we are given two Weighted strings \(W_1\) and \(W_2\) and a threshold \(\tfrac{1}{z} \) on probability, and we are asked to compute the shortest (standard) string S such that both \(W_1\) and \(W_2\) match subsequences of S (not necessarily the same) with probability at least \(\tfrac{1}{z} \). Amir et al. showed that this problem is NP-complete if the probabilities, including the threshold \(\tfrac{1}{z} \), are represented by their logarithms (encoded in binary).