I have given thought to the software already described by myself in an earlier posting and it is easily modified to find such complementary sub-sequences. Hence, the question posed.
William,
one way to approach this (that has gotten a lot of attention already) is the use of suffix trees or suffix arrays to determine the longest common prefix/subsequence (Applications in http://en.wikipedia.org/wiki/Suffix_array). If errors are considered, than the process is combined with a dynamic programming algorithm (first introduced by Landau and Vishkin, I believe in http://u.cs.biu.ac.il/~amir/gadi.chapter.pdf). A bit of tweaking is probably necessary to account for both direct and inverted patterns (as in tandem repeats and palindromes/inverted repeats) and possibly to allow the discovered complementarity to overlap itself.
I notice that with a slight alteration of the shustring software (that I have already sent you), the output will be pairs of complementary strings and their locations.
And, yes, complementarity within just one strand of DNA; no consideration of inverted transcription.
May be you can use two suffix array, one for the upstream and one for the downstream, and compare them.
I am not seeking to discuss technique for detection. My question concerns the utility of such knowledge; this is a philosophical concern. This question stems from observation about conflict between tDNA insertions in Arabidopsis research lines and how such conflicts might be avoided; conflicts like insertion silencing. Since I can already find shustrings by a comparison method, I can modify the comparator of my algorithm to match on complementarity instead of on difference of nucleotide residue, and so find complementary strings of large length. So, one reply of comment appropriate to this discussion will address the likelihood of finding large complementary sequences on one strand of an arbitrary chromosome.
There are a lot of long complementary sequences on the human Y chromosome. http://phylogenous.wordpress.com/2010/09/22/y-chromosome-vi-palindromes/
Thanks for the link.
I believe that the author's use of the term Palindrome is improper, as his example is of sequences that are complementary, not identical backward and forward. Also, the example from the suggested Molecular Biology text shows the complementary base pairing of a double strand, so the example does not correspond to the author's argument. Still, the point is well taken, and indeed it is easy to find both complementary strands and palindromes.
- Badges
- Science topic
- Similar topics
- Biological Science
- Genetics
- Genetic Analysis