Re^4: genetic algorithm for motif finding

By /msg you said:

Re Re^4: genetic algorithm for motif finding The problems start with the simple ones, you have to solve them to get further. I found for example EDTA or RNAS to be a bit more complicated.

I have no idea if you have anything to do with the Rosalind site; but if you do, please do not be offended by this. It's just my opinion :) Your attempt to help me is much appreciated.

The problem I see with the Rosalind site is this: The tutorials and challenges are all geared to leading the programmer to solve the problems in one particular way. In the case of the two examples you cite are Edit Distance & graphs respectively. Both of which are a problem.

Edit distance.
There are many different algorithms for this Levestien; Wagner-Fischer; etc. and they are all horribly inefficient O(mn) compared to simply xoring teh strings and counting the nulls:
```
$n = ($a ^ $b ) =~tr[\0][];
[download]
```
Which is O(2N). And as both N are implemented in C (opcodes); they results can be orders of magnitude faster for DNA length strings.
Graphs.
Unless a new graphs module has appeared on the scene (cpan) recently; implementing graphing algorithms in Perl is horribly slow and hugely memory hungry.
Graphs lend themselves to being implemented using OO-style with a Nodes/Edges/AdjacencyMatrix/Attributes/Weights/etc classes all based around blessed Hashes (or worse!) and rendering the simplest of graphs constructed with them huge, cumbersome and slow.
The idea of solving genomic problems by creating graphs of entire genes with every base a node and edges linking the pairs is just a non-starter in Perl using native Perl graphing libraries. They just require too much memory and processor.
That is probably why so much of genomic work is parceled up and sent of to mainframes or clusters (BLAST servers and the like) with gobs of memory and huge processing power, to do the donkey work. But that in turn creates its own set of knock on problems:
1. These batch processors tend to produce far more information than most querants require. (say) Producing edit distances and other quality statistics; when often only a boolean yes or no is required.
2. Their output is often-as-not in a form -- multi-line 'carded' records and the like -- which make extracting the required results almost as complex as solving the original problem.

The silly thing is, that X86-64 class machines are actually very good at string processing; and many of the tasks can be tackled very efficiently using them; once you stop viewing the problems in terms of graph theory and look for string manipulation solutions.

That's why when these DNA/RNA problems come up; I ask for and try to extract very simple descriptions of the problems that aren't couched in either biogenetic terminology nor the mathematical symbolism applicable to just one approach to solving the problem. Unfortunately, these requests usually fall on deaf ears.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^4: genetic algorithm for motif finding Download Code

Replies are listed 'Best First'.
Re^5: genetic algorithm for motif finding by choroba (Cardinal) on Aug 15, 2013 at 17:01 UTC
I am just a normal user of the site. I use it rarely as a training of my coding skills, so no offence taken. Well, if insertion and deletion are also involved in the edit distance, a simple XOR cannot solve the problem. The graph solution to RNAS would be terribly slow (not only in Perl) and one would run out of time (there is a 5 minutes limit). You have to find a way how to solve the problem without going into representing the graphs at all. That was what took me some time, once I knew the algorithm, the implementation was a routine. It is true that most of the simpler problems can be solved by one-liners in Perl. The site does not care about how you solve the problems: you just download the test data and have 5 minutes to upload the solution. That gives us Perlers an easier start on the ladder. I agree with you that the jargon used by some bioinformaticians is incomprehensible. I fear the reason sometimes is they do not understand the underlying problems in proper detail, it is just a form of handwaving. لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ	[reply]

Replies are listed 'Best First'.

Re^5: genetic algorithm for motif finding
by choroba (Cardinal) on Aug 15, 2013 at 17:01 UTC

Well, if insertion and deletion are also involved in the edit distance, a simple XOR cannot solve the problem. The graph solution to RNAS would be terribly slow (not only in Perl) and one would run out of time (there is a 5 minutes limit). You have to find a way how to solve the problem without going into representing the graphs at all. That was what took me some time, once I knew the algorithm, the implementation was a routine.

It is true that most of the simpler problems can be solved by one-liners in Perl. The site does not care about how you solve the problems: you just download the test data and have 5 minutes to upload the solution. That gives us Perlers an easier start on the ladder.

I agree with you that the jargon used by some bioinformaticians is incomprehensible. I fear the reason sometimes is they do not understand the underlying problems in proper detail, it is just a form of handwaving.

لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

[reply]