What are the applications of DNA or RNA pattern matching? [closed]

Question

I'm assuming we don't do pattern matching in DNA or RNA for the fun of it. So I'd like to know what are the applications of pattern matching or where does it fit in in larger applications?

I'm a computer scientist and when studying certain topics in CS we see a lot of references to applying algorithms to areas of biology or genetics one of which is applying text pattern matching algorithms to DNA to find sub sequences. Whenever I see those kinds of examples I think "Oh that's pretty cool" but then I don't see how it's applied in the real world for benefit and I can't find anything to suggest where these algorithms are applied in these fields.

Answer 1

One useful application of pattern matching is for DNA sequence motifs. As an example of a direct application, there is a class of proteins called transcription factors (TFs), which bind to DNA and regulate the expression of genes. There are many TFs. Each TF likes to bind to its particular conserved sequence of DNA, with some wiggle room for some parts of the sequence.

Algorithms for finding and scoring these patterns (and mismatches in patterns) is important for identifying regions where regulation occurs, which proteins are involved, and for answering biological questions related to gene regulation and basic biological functionality — and malfunction, in case of disease.

Answer 2

These algorithms are used quite a lot, and I will touch only a few aspects:

• Genetic sequence alignment. Different (but still closely related) organisms have very similar genetic sequences, which differ only at some positions due to point mutations, which can be nucleotide substitutions (another letter in a sequence) or insertion/deletion of a few nucleotides. Many biological questions such as studying new coronavirus strains, predicting genetic diseases, and identifying cancerous cells are based on such sequence comparisons. This requires aligning many sequences, using the appropriate algorithms. This may be not hard for two sequences, but for hundreds or thousands of them it may require serious computational effort.
• Sequencing reads mapping Much of the current progress in genetics is due to the advent of the next generation sequencing, also called massively parallel sequencing, as opposed to Sanger sequencing used in the first human genome project (see here, for example). The basis of this technology is splitting the genetic sequence (a few billion nucleotides in a human) into small fragments of a few hundred nucleotides long and sequencing them simultaneously. One then faces the problem of putting them back together, which can be achieved either via matching them to a known sequence for a similar organism (sequence mapping) or by putting the reads together on the basis of their similarity (sequence assembly). There exist multiple sophisticated bioinformatic tools for achieving this (BWA, bowtie2, TopHat, Megahit to name just a few, so that you can google them).
• Blasting Another application, closely related to my first point, is quickly identifying the sequence as belonging to a certain gene of a certain organism by comparing it to a large database. BLAST is one of the well-known collections of tools for doing this.
• Just to mention (only a bit) more exotic applications: the algorithms associated with parsing context free grammars are used for RNA structure prediction.

Durbin's book is a good casual reading (for somebody with a computer science background) to get an overview without knowing too much biology.

Answer 3

The applications can be categorized based on whether you study the sequence for analysis, or for DNA synthesis and assembly.

In addition to TF patterns mentioned in this answer, other patterns for DNA binding proteins, enchancers, promoters, and the Kozak sequence (GCCGCC[A|G]CCATGG..) may also be useful for discovery of ORFs (genes) / regulation.

Certain methylase enzymes recognize a DNA pattern. For example EcoKI methylates adenine in AACNNNNNNGTGC (2nd A) and its reverse complement, GCACNNNNNNGTT (3rd A). Another such enzyme is EcoBI. This is useful for finding methylation sites, which may interfere with DNA restriction or expression.

Some restriction enzymes also recognize a DNA pattern: HinFI recognizes

5'GANTC
3'CTNAG

Other such enzymes are EcoP15I, EcoRII. Finding these sites are very important for designing a DNA cloning or manipulation experiment.

For DNA synthesis, it is useful to avoid homopolymers (N+) and repeated k-mers and hairpins (a sequence segment which has a reverse complement "nearby") as these can cause problems during synthesis.

Direct, tandem or inverted repeats can cause problems during cloning.

Finally, a perhaps trivial example is matching a polypeptide sequence, using DNA, as the genetic code is redundant. An example would be searching for target peptides in a protein.

Answer 4

To extend on the existing answers I would say that pattern matching algorithms are at the core of bioinformatics, certainly any NGS realted bioinformatics. The Smith-Waterman algorithm and its variants are probably the most used https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm .

Reference genome assembly (the human genome project for example) is based on kmer based sequence matching. Variant calling is based on mapping sequence to this reference, so thats pretty much all clinical bioinformatics. And a million other tools - one random example is dectecting horizontal gene transfer of antibiotic resistence genes.