4 ms·

The biggest surprise for many, myself included, around genomic software that arose after the Human Genome Project was that the useful things people wanted to do

The biggest surprise for many, myself included, around genomic software that arose after the Human Genome Project was that the useful things people wanted to do with sequence data didn’t need need the expressiveness provided by PCRE, et. al. String algorithms have a minor role in day-to-day genomics.

inciampati 5y ago
Really? String algorithms (in the stringology / compressed data structures sense) are the foundation of virtually every operation in genomics that interacts with raw data. Have you ever aligned a sequence? Regexes are not important. But they are a tiny bit of string algorithms.
- jacquesm 5y ago
  > Have you ever aligned a sequence? Not the op. Yes, I've done some work on this, then tested it against some of the software used in various environments for this kind of work and more than once spotted alternative, more efficient alignments. The practical upshot of that is that I ended up wondering if there is ever a serious bug found in such a piece of software if it shouldn't automatically cause all papers that used the software for their work to be at a minimum flagged for an additional round of review as well as potentially from being disqualified. What also struck me is that the people using this software treat it like a black box, they have absolutely no way of verifying that what it did it did right.
  - Q6T46nT668w6i3m 5y ago
    You’re making a good point that’s usually ignored outside of genomics. Inside genomics, alignment is treated, correctly, as a probabilistic rather than deterministic process (i.e., an alignment is not “right” or “wrong”) and many choose to consider multiple alignments.
    - jacquesm 5y ago
      That works as long as you don't try to do things like phylogenetic trees, the ordering becomes so critical that even one swap can make things look like the order was the reverse. Of course you should never rely on just the one datum but the temptation to do so and to treat the software as correct is large due to the pressure to publish rather than to hold back and wait until there are multiple pieces of evidence.
      - Q6T46nT668w6i3m 5y ago
        Are you speaking from experience?
        jacquesm 5y ago
        I was first hand witness to some stuff that I doubt would withstand prodding but I'm not at liberty to talk about it.
  - jltsiren 5y ago
    There are probably serious bugs in all sequence alignment software, but it's unclear how much it does matter. Downstream analysis must assume that the alignments contain all kinds of known and unknown errors anyway. The sequence alignment problem itself is so ill-defined and there are so many sources of bias and errors, from data to algorithms, from code to reference sequences, from instruments to sample preparation, and including your definition of truth, that you often can't say confidently whether the alignment is correct. The scale of the data is often also big enough that you have to make deliberate trade-offs between costs and correctness.
    - jacquesm 5y ago
      > Downstream analysis must assume that the alignments contain all kinds of known and unknown errors anyway. It must, but it doesn't always do so.
- Q6T46nT668w6i3m 5y ago
  I have! I even regularly contribute to a popular alignment application! Regardless, you’re absolutely correct and I should’ve chosen my words more carefully. Especially about the relationship to information theory. I meant “regular expressions, LL, LR, LALR, etc.”
  - deleted 5y ago
    [deleted]
dekhn 5y ago
There was a popular protein fragment recognizer using a pattern language simiilar to regular expressions (https://en.wikipedia.org/wiki/Sequence_motif#PROSITE_pattern_notation https://en.wikipedia.org/wiki/Sequence_motif#PROSITE_pattern...) but this only works on closely related sequences. As mentioned in other comments, sequence analysis is probabilistic, so "matchers" instead tend to be statistical models, like HMMs. There is a rich relationship between statistical models like HMMs and parsing theory.

inciampati 5y ago

Really? String algorithms (in the stringology / compressed data structures sense) are the foundation of virtually every operation in genomics that interacts with raw data. Have you ever aligned a sequence? Regexes are not important. But they are a tiny bit of string algorithms.

jacquesm 5y ago
> Have you ever aligned a sequence? Not the op. Yes, I've done some work on this, then tested it against some of the software used in various environments for this kind of work and more than once spotted alternative, more efficient alignments. The practical upshot of that is that I ended up wondering if there is ever a serious bug found in such a piece of software if it shouldn't automatically cause all papers that used the software for their work to be at a minimum flagged for an additional round of review as well as potentially from being disqualified. What also struck me is that the people using this software treat it like a black box, they have absolutely no way of verifying that what it did it did right.
- Q6T46nT668w6i3m 5y ago
  You’re making a good point that’s usually ignored outside of genomics. Inside genomics, alignment is treated, correctly, as a probabilistic rather than deterministic process (i.e., an alignment is not “right” or “wrong”) and many choose to consider multiple alignments.
  - jacquesm 5y ago
    That works as long as you don't try to do things like phylogenetic trees, the ordering becomes so critical that even one swap can make things look like the order was the reverse. Of course you should never rely on just the one datum but the temptation to do so and to treat the software as correct is large due to the pressure to publish rather than to hold back and wait until there are multiple pieces of evidence.
    - Q6T46nT668w6i3m 5y ago
      Are you speaking from experience?
      - jacquesm 5y ago
        I was first hand witness to some stuff that I doubt would withstand prodding but I'm not at liberty to talk about it.
- jltsiren 5y ago
  There are probably serious bugs in all sequence alignment software, but it's unclear how much it does matter. Downstream analysis must assume that the alignments contain all kinds of known and unknown errors anyway. The sequence alignment problem itself is so ill-defined and there are so many sources of bias and errors, from data to algorithms, from code to reference sequences, from instruments to sample preparation, and including your definition of truth, that you often can't say confidently whether the alignment is correct. The scale of the data is often also big enough that you have to make deliberate trade-offs between costs and correctness.
  - jacquesm 5y ago
    > Downstream analysis must assume that the alignments contain all kinds of known and unknown errors anyway. It must, but it doesn't always do so.
Q6T46nT668w6i3m 5y ago
I have! I even regularly contribute to a popular alignment application! Regardless, you’re absolutely correct and I should’ve chosen my words more carefully. Especially about the relationship to information theory. I meant “regular expressions, LL, LR, LALR, etc.”
- deleted 5y ago
  [deleted]

dekhn 5y ago

There was a popular protein fragment recognizer using a pattern language simiilar to regular expressions (https://en.wikipedia.org/wiki/Sequence_motif#PROSITE_pattern_notation https://en.wikipedia.org/wiki/Sequence_motif#PROSITE_pattern...) but this only works on closely related sequences. As mentioned in other comments, sequence analysis is probabilistic, so "matchers" instead tend to be statistical models, like HMMs. There is a rich relationship between statistical models like HMMs and parsing theory.