Databases
StackOverflow2013
Postsdbo
POstring-match problem
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POstring-match problem
    primarykey
    data
    text
    <blockquote> <blockquote> <p>EDIT 2: I managed to find the solution with suffix trees <code>Tree::Suffix</code> perl package. Thanks to MarcoS for the <code>trie</code> idea. I figured out from that, that suffix trees could be used as well. The <code>Tree::Trie</code> perl package is implemented as hash of hashes and I guess that's the reason it slow. I tried it and then went back to <code>Tree::Suffix</code>. Thanks to all others for their links to different algorithms. I am already trying to write code for every algorithm mentioned here myself as a learning process </p> <p>EDIT 1: I changed the title from <code>perl string-match problem</code> to <code>string-match problem</code>. </p> </blockquote> </blockquote> <p>Suppose that I have two strings, say,<br> <code>S1 = ACGAGGATAGTATGCCACACAATGAGTACCCGTAC</code><br> <code>S2 = CAGTATTGCACGTTGTAAAGTTACCCAGGTACGATGACAGTGCGTGAGCATACGAGGATAGTATGCCA</code> </p> <p>I initially wanted to check for the occurrence of string S1 (with no or 1 mismatch) in S2. And I have already written the <code>perl</code> code for that.</p> <p>Now, I would like to develop on it to </p> <blockquote> <p>1) Search for k-mismatches of S1 in S2.<br> 2) Search for the occurrence of a <code>prefix</code> (yes, prefix, not suffix), of S1 in S2. If you look at the example, the string: <code>ACGAGGATAGTATGCCA</code> occurs at the end of S2 which is the beginning of S1.<br> 3) If possible, search for the prefix with k-mismatches. </p> </blockquote> <p>The catch is that I have about 100 million such S2 strings. S1 however remains the same and is of a defined constant length for a given problem. Is there an efficient algorithm in the literature that I could use for this problem of mine?</p> <p>S1 varies between 50 and 80 characters. Also, I am mostly interested in solving <code>problem 2</code> at first. </p> <p>Thank you very much.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USArun
    1. USArun
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COI can't believe it would be efficient to write that in perl unless you can find a native module to implement the k-mismatch algorithm.
      singulars
      1. POstring-match problem
      1. USAlnitak
    2. COCould a [Trie](http://en.wikipedia.org/wiki/Trie) be helpful for your purposes?
      singulars
      1. POstring-match problem
      1. USMarcoS
    3. COPerhaps see: http://stackoverflow.com/questions/1672782/fastest-way-to-find-mismatch-positions-between-two-strings-of-the-same-length
      singulars
      1. POstring-match problem
      1. USJoel Berger
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload