Darwinbots Forum
Code center => Suggestions => Topic started by: shvarz on June 09, 2005, 03:49:22 PM
-
The true fault of the current sexrepro system in DBs is not really the choosing mates or staying together for long enough time or the lack of diploidy - all of these are circumstantial for sexual reproduction. The real advantage of sex is recombination - that is re-assortment of different regions of DNA. Recombination allows getting rid of bad mutation, escaping mild forms of the muller's ratchet and joining two good mutations that arose independantly.
Recombination is the true blessing of sex and our poor bots are missing out on it!
Right now during sexrepro genes are simply mixed up randomly, gene 1 from bot 1, gene 2 fro bot 2, gene 3 from bot 1 and so on. The problem with this approach is that the program actually does not compare the genes, so that if one of the bots has an extra gene inserted, then the product of this "recombination" will be a truly messed up bastard. In real life there are mechanisms that align DNA and make sure that exchanged pieces of DNA are actually at least remotely similar.
Another problem is that duplicted genes can't recombine with each other. Here is what often happens in real life: you start with 1 gene, then duplicate it. Now you have copies A and B. Since the two copies are similar, then during sexual reproduction you can align copy A with copy B:
DNA 1: A-----B
DNA 2: ------A-----B
After recombination:
DNA 1: A----A----B
DNA 2: ------B
This is a very important mechanism for duplicating genes, re-assorting mutations and activating non-functional copies of genes. And our bots are missing on this too!
So, what can we do? We can't just align DNA in DBs looking for similar regions. The algorithms for that are so complex that it is impossible to do real-time (not until quantum computers appear).
I think I have a solution:
When DNA is loaded into the program, we introduce specific unique markers into its structure after every command. Something like random 16-digit numbers (this can be done behind the scene, so that it we can still look at the DNA). These numbers cannot be mutated, but they can be duplicated/deleted along with DNA that surrounds them. During sexual reproduction, the newly formed DNA starts from one of the parents and with some probability it switches to DNA of the other parent. During the switch, program looks for the unique identifier at the place of recombination in the DNA of the other parent. If there is none, then it returns back to the first parent, if there is one, then it continues from the spot where that identifier is, and if there is more than one, then it picks one of them randomly and continues from there.
This would essentially allow recomabination to happen, along with all the advantages it brings. What do you think?
-
I was thinking of using centromeres to allign two chromosome threads.
The centromeres are defined for a specific spot on the DNA of two strands, with crossing over occuring based on that centromere as a reference point.
I talked about this in the junk DNA thread just now and I had a post in suggestions not too long ago.
I think crossing over (the current version doesn't count for this stipulation, since it's more like bacteria gene transferance anyway) should only be allowed between chromosomes that are bound together with a centromere.
-
It does not solve the problem of crossing over non-similar sequences. And it does not allow non-reciprocal recombination (between different copies of the same gene).
-
Well, centromeres are unlikely to develop between disimilar chromosomes. If they do, the chromosomes will eventually become similar through crossing over. Like shuffling a deck of cards. If I have one deck of all red, and another of all black, after enough shuffles they'll become randomly distrubted into red and black.
That is, if you cross over from chromosome A 50 units from its centromere, and do the same for B, it doesn't matter if they're similar or not. If they're not similar, the result is probably a mess. If they are identical, you get no effect.
As for non-reciprocal recombination, no, it doesn't address it. Give me some time to think about it (I'm tired right now).
-
From what I can tell, non-equal crossing over is the exception instead of the norm. That is, it's a mutation.
I was thinking of adding a portion to the mutations tab for crossing over errors. This would go in there. You could set how far off the length is wrong, and the chance of such an error occuring each time crossing over occurs.
As far as I can tell, this unequal crossing over is primarily between neighbor areas. That is, you won't get a massive slip in the chromosome pairing very often.
Although occassionally the chromosomes will split on different ends of the centromere. But that's a massive mutation that rarely produces meaningful results.
-
Yes, it is a mutation, but it is such a good, nice mutation that it was the direct cause of many-many-many cool things evolving. Like most of our immune system, or taste and smell receptors and so on... And that's just in eukaryotes.
The problem with counting from centromere is the same as counting from the beginning of DNA - it does not solve anything. A single insertion or deletion and bots can't recombine anymore. Besides, you are still thinking in recombining genes, but my method allows recombination to occur anywhere, and it almost always will produce meaningful working bot. In addition, it will allow repair mutations using second strand as a template if we decide to go diploidal.
-
A single insertion or deletion and bots can't recombine anymore. Besides, you are still thinking in recombining genes, but my method allows recombination to occur anywhere, and it almost always will produce meaningful working bot. In addition, it will allow repair mutations using second strand as a template if we decide to go diploidal.
I'm thinking in terms of breaking off whole areas of the chromosome and reattaching them elsewhere, quite irregardless of genes at all.
As you insert a new condition in one chromsome, then the strands become unequal and an unequal crossover occurs ipso facto. The centromere, no matter where it is spatially at first, will eventually become more or less in the middle since the DNA is shuffled around it.
If nothing else, the centromere system solves other problems as well as recombination, and it's older. From a few simple rules I can construct most of the rules of eukaryotes.
Centromeres allow chromosomes to be paired within the genome. Centromeres can be developed naturally from repetitive sequences. Centromeres allow chromosome pairing to be epigenetic. Centromeres ensure incentive for similar chromosomes to become paired since that way they'll for sure move to opposite ends during mitosis. And they allow crossing over to occur by simple breaking of both strands and swapping pieces.
ie:
chromo1:
1-1-1-1-1-1-1
chromo2:
2-2-2-2-2-2-2
after one crossing over event:
1-1-1-2-2-2-2
2-2-2-1-1-1-1
It doesn't even have to occur at a gene break point. It can occur anywhere. If they're unequal lengths:
1-1-1-1-1-1-1-1
2-2-2-2-2-2-2
after one crossing over event:
2-2-2-2-1-1-1-1
1-1-1-1-2-2-2
-
If I can add to my last post:
I was going to model crossing over on the Holliday Model (http://www.web-books.com/MoBio/Free/Ch8D2.htm).
-
Centromeres is a nice idea. And it can work together with my UID (unique ID) system in parallel.
I still think UID system is a lot more powerful, because for recombination it allows all that your system does and then some more.
Imagine that two people start evolving the same bot, then share through internet. By that time genomes changed a lot, new genes were introduced, mutations accumulated, some commands got deleted. Your system of simply counting off a certain number of commands and switching will produce only non-viable bots. My system will allow them to recombine and almost always create a viable bot.
Another example:
imagine a series of sequencial commands:
a-b-c-d-e-f-g
Say one of the bots got an insertion (I) that really increases its fitness
A-B-I-C-D-E-F-G
Bots are reproducing sexually, so that this bot must mate with an old-style bot. Your system creates a number of different bots with this insertion, with general types like this:
a-B-I-C-D-E-F-G (alive)
A-B-I-d-e-f-g (dead)
A-B-I-C-D-f-g (dead)
Basically, the only survivable bots are those that crossed over before the insertion. Any time after - and the whole gene is messed up. Unless cross-over happens in junk DNA.
My system will always make a viable bot, because it aligns the DNA correctly. It does not introduce any additional insertions/deletions during reproduction, so that the chances for off-spring to be viable are much-much higher!
P.S: Holliday model assumes you have aligned the DNA first.
-
Okay, correct me if I'm wrong, but:
a-B-I-C-D-E-F-G (alive)
simple insertion of new instruction, and trading of chromosome arms.
A-B-I-d-e-f-g (dead)
small deletion and trading of chromosome arms (remember that for DNA missing a letter is disaterous because it makes all words downstream meaningless. But for us each DNA instruction is atomic, so in our system such an event would be like DNA losing the coding for a single amino acid).
A-B-I-C-D-f-g (dead)
insertion of new instruction and deletion of E/e.
Neither deletions nor insertions are automatically lethal, unless they're in a gene that codes for important behavior. And then you shouldn't be mutating it anyway.
That said, some mechanism like polymerase that zips up two paired chromosomes for crossing over could be useful. How does real DNA pair up the chromosome? How do polymerases do it? Maybe we can do something similar.
Mind you I'm not against an ID system, I just want to understand the problem and solutions possible before picking one.
-
Shvarz, your UID system gave me an idea. I think UID would be a good thing, being basically a shortcut to actually comparing dna portions to look for similar parts. On the other hand, it would require changes in the way dnas are stored. What do you think of this: without the need to modify anything anywhere else, we just change the sexual reproduction routines. We insert a new routine which calculates a number (let's call it idcode) from each gene (say, just by calculating the sum of the type-value sequence in the gene, or something like that). Then, we take each gene from one of the parents, and we couple it with the gene with the closest idcode number. When genes have been coupled, we take one of them from each parent and build a new dna. We should decide what to do with genes that remain uncoupled.
Now, to be clear, an example. Say we have a gene
cond
*.eye5 0 >
start
10 .up store
stop
If we assign a value to each instruction, variable and number, we can easily make a sum of these values and obtain a code which is not unique for that gene, but has very good chances to be unique in that dna. An important feature of this code is that, unlike a hash code, it is only slightly changed by little variations.
Now, say that the calculated idcode for this gene is 100.
A mutated copy of this gene, say
cond
*.eye7 0 >
start
10 .up store
stop
may have idcode=102
Now, if we have two dnas, with genes: (where 1, 2, ... are different genes, 1a, 1b,.. are slightly mutated copies of the gene 1, and there's an idcode associated to each gene)
dna1...............dna2
1-100.............1-100
1-100.............2-324
2-324.............3a-64
2a-320...........3b-66
3-60...............4a-410
4-400.............5-150
4b-390
You understand that it is relatively simple to mix these two dnas. You should couple each gene of dna1 with one of those with more similar idcode on dna2. You may decide randomly which gene to couple if there are two or more with similar idcode. For example, you may decide to couple either gene2 or gene2a from dna1 to gene2 in dna2.
If you wish to have a more fine crossing, you may even decide to go further and split the coupled genes somewhere inside them and mix the two ends.
-
The only problem with that is its still gene-centric. We should be moving away from treating the genes as whole units.
-
I'd prefer to leave apart the discussion about possible new structures for the dna language, and implement rapidly this kind of sexual reproduction. If we (you) are ever going to change the dna structure, you'll change also this, among many other things. But let's have immediately what we can have now.
-
We should build up from A to B. The code is already fairly strung out and inconsistant. Coding something that just needs to be coded over later is wasteful.
And remember what's wrong with the current sexual reproduction system: It's gene centric. If all you're after is mixing up the genes between bots, it does just fine.
A more complex, chromosome based system is what we should be considering, and working toward in small but self consistant and robust steps.
-
We should build up from A to B. The code is already fairly strung out and inconsistant. Coding something that just needs to be coded over later is wasteful.
First, it's not said that we're really going to change the dna language. I don't really see any need for that, except maybe going in the direction of less programmability and understandability of the language itself.
And remember what's wrong with the current sexual reproduction system: It's gene centric. If all you're after is mixing up the genes between bots, it does just fine.
It seems to me that nobody said that. Shvarz's point, that is correct, is that the mixing of genes how it is made now don't work when genes are duplicated (because sometimes the zig-zag procedure cuts off a valid gene). But this method solves the problem perfectly, and it's also biologically sound.
-
Nums:
Here is what you are missing: Both parental genotype and the genotype with insertion are viable genotypes, tested by natural selection. The genotype with insertion is more fit than parent's genotype. We don't know what the fitness is for genotypes with insertion and additional mutations (they don't have to be lethal, I just gave it as an example, but they are very likely to be less fit). The goal of sexual reproduction is to allow spread of the beneficial mutation in the population, so that it could get combined with another beneficial mutation. At this point you want to reproduce the mutated region of DNA faithfully, you don't want to introduce additional mutations.
Carlo: I am all for shortcuts as long as programmers actually want to spend their time on it. Does not look like Nums is too excited about doing double-work, though <_< It is a valid substitute for now and it will fix sexrepro to some degree. As Nums pointed out, it has its weaknesses too - it is still gene oriented. Also, it is not fool-proof for genomes that got significantly diverged during parallel evolution. The UID system has its ups and downs too. The major down is that it makes it more difficult to look at DNA with all those numbers getting in the way. Here are the pluses:
1. Recombination
2. Backwards-compatible (all previous DNA's can still be used).
3. Allows alignment of genotypes to look for evolution patterns. Have you seen my file tracking evolution of Dom ternia? I had to do all that alignment manually - major pain in the ass.
4. Can be optional - turn it off and the program removes all UIDs and keeps using the old notation. UID system is really only useful for evolution sims, everyone else can still use the old system.
5. It automatically prevents cross-breeding between different species (even if they have exactly the same DNA). Yet it still allows occasional breeding between organisms that evolved from common ancestor.
-
If you can find a link on how real organisms line up their chromosomes (I looked but didn't find anything), that would rock! I know it's some sort of polymerase, I just don't know how it works.
-
I have read this repeatedly tring to understand it all but I'm starting to think I can't lol.
I get you need to swap only similar genes for offspring not to be messed up. But my first thought was that similar genes would share activation conditions only. Does it matter what the body of the gene contains? Two genes with the same activation conditions will probably not be the same but will probably do the same sort of thing. So can't you just compare the conditions for genes?
-
Does not look like Nums is too excited about doing double-work, though dry.gif It is a valid substitute for now and it will fix sexrepro to some degree.
I can assure you is a rapid work. By contrast, all other proposals seems much more difficult to realize, still are rather undefined, and involve much rework of the code in the rest of the program.
As Nums pointed out, it has its weaknesses too - it is still gene oriented.
You can even split the coupled genes inside them, if you want, instead of chosing one or another.
Also, it is not fool-proof for genomes that got significantly diverged during parallel evolution.
This is correct, because individuals which have diverged too much should not interbreed. That's speciation.
On the other hand, your system
5. It automatically prevents cross-breeding between different species (even if they have exactly the same DNA). Yet it still allows occasional breeding between organisms that evolved from common ancestor.
Which is a blatant violation of one of the principles of DB, that is, that species name is just a comfortable label and has no meaning inside the simulation.
As for the pluses of your system, probably there is something that you should know: that is, that there are standard and well known routines to calculate the common parts and similarities between to texts. And they are relatively fast. So, UID in principle is useless. Programmers commonly use text editors which are able to highlight the differences between two source codes. There are many bioinformatic tools that calculate the differences between two or many textfiles or genefiles.
For example:
gendistance: this is free:
http://monod.uwaterloo.ca/downloads/gencompress/ (http://monod.uwaterloo.ca/downloads/gencompress/)
calculates the distance matrices between a number of textfiles. Then you can build a phylogenetic tree. I used it once for DarwinBots (in conjunction with phylip I think). (oops.. now that I remember... I even made a tool to automatically build archives to pass to gendistance... )
And here you can find a wide list of free tools for comparing text files:
http://www.thefreecountry.com/programming/...omparison.shtml (http://www.thefreecountry.com/programming/filecomparison.shtml)
-
By the way, this is an example of a phylogenetic tree generated with the data from an internet shared simulation (about one year and a half ago, maybe). Each leaf of the tree is a robot (all of the same species), the numbers stand for generation and mutations number. The tree is unrooted (every leaf can be taken as root). The starting data were the pure and simple dnas of the robots.
+---------------------1
+------------8 +1c-145-95
! !
! +---------------------1c-119-77
+--------15
! ! +-----------1c-154-102
! ! +-----------------4
! ! ! +-----------1c-156-103
! +--13
+---------20 ! +----------------1c-164-107
! ! +-------------7
! ! +----------------1c-168-120
! !
! ! +---------------------------1c-189-118
! +--------------11
! +---------------------------1c-198-139
+--24
! ! +---------1c-225-155
! ! +------------------------------2
! ! +----19 +---------1c-229-156
! ! ! !
! ! +------21 +---------------------------------------1c-233-162
! ! ! !
! ! ! ! +---------1c-235-150
! +-23 +-----------------------------------3
! ! +---------1c-235-156
! !
! ! +-----------------------------------1c-236-156
! +----------------16
! +-----------------------------------1c-238-165
-26
! +-----------------------------1c-201-138
! +--------12
! ! +-----------------------------1c-218-154
! +--------18
! ! ! +------------1c-211-142
! ! +--------------------------5
! ! +------------1c-212-148
! +----22
! ! ! +------------------------------1c-242-172
! ! ! +----14
! ! ! ! ! +-------------1c-245-176
! ! ! ! +----------------6
! ! +----------17 +-------------1c-254-185
+--25 !
! ! +--------------------------1c-257-178
! +--------10
! +--------------------------1c-265-189
!
! +--------------------------1c-265-192
+----------------------------9
+--------------------------1c-266-180
-
f you can find a link on how real organisms line up their chromosomes (I looked but didn't find anything), that would rock!
As far as I can tell, this is still unknown! The general feeling is that DNA sequences are somehow aligned alonside each other in a very accurate manner (down to a base). We know only one way to accurately align DNA strands - unwind the double helices and allow base-pairing of homologous regions (do you understand me here? sounds a bit too technical). There is some evidence that this happens, but no definite proof. Google for synaptonemal complex and recombination to find some pages that talk about this.
-
Which is a blatant violation of one of the principles of DB, that is, that species name is just a comfortable label and has no meaning inside the simulation.
Sometimes you don't want it to be just a label. Say you want to compare fitness of two closely related organisms that reproduce sexually - then you don't want them to inter-breed.
there are standard and well known routines to calculate the common parts and similarities between to texts. And they are relatively fast.
Well, in my lab there are people who study evolution of viruses and they often need to build phylogenetic trees for them. They are using the best software available and thier alignments usually take overnight and sometimes go for several days. Which makes me think that any program that does this in a fraction of a second is a sham. Well, maybe it can do some half-assed job, but I am sure it will stumble over some of the things that evolution does.
BTW, I don't know about text editors that programmers use, but Word gets totally fucked up when you try to compare documents with several parts moved around. I tried it, it does not work :)
Basically, if you can do it - great! I won't complain. But I don't see why UID system can't be implemented - it is very powerful and yet it is very easy to add...
-
Okay I understand the problem a bit better now.
A ID system would work, but you're right, it makes DNA messy. Instead we could define a particular series of commands, something that's likely to be "Junk", and have the program "zip" up homolgous chromosomes starting at these points. When an inconsistancy occurs, you stop.
Or instead of Junk DNA, we could use a special command. Either works (although a command just for this seems overkill to me).
If you have enough such commands, every inconsistancy is effectively isolated. If not, you suffer from problematic unequal crossovers. Benefit is that the DNA still becomes readable without alot of fluff.
We could even have the DNA 'correct' itself if it finds an inconsistancy. We could also change how large the inconsitancy needs to be to stop the 'zipping' up.
Only zipped up regions can have a crossing over event occur.
That's consistant with everything I understand about crossing over. Tell me how well that works shvarz.
-
Sometimes you don't want it to be just a label. Say you want to compare fitness of two closely related organisms that reproduce sexually - then you don't want them to inter-breed.
The best way to solve this problem is to require a kind of 'handshake' signal that both bots want to mate.
I was thinking of implementing sexual reproduction through ties. So both bots would have to set a variable to true to allow the mating to occur. No rape in DB!
BTW, I don't know about text editors that programmers use, but Word gets totally fucked up when you try to compare documents with several parts moved around. I tried it, it does not work :)
He's right, I haven't found a good document comparing utility that can recognize that I moved text segment A from the top of the document to the bottom. Windiff just tells me they're different in those places, which isn't particularly useful beyond a point.
-
yea I was looking for a better program then windiff too , no luck yet. I need binary compare though.
-
I made a modification to Windiff and put it on the FTP a while ago. It ignores capitalizational differences.
But that's sort of off-topic, isn't it. :rolleyes:
-
Only zipped up regions can have a crossing over event occur.
This is a possibility... We can align very short stretches of DNA to zip them up. What we can do is this: At some point during copying the DNA, program decides to cross-over. It then takes N next commands (5-10 should be enough; make it user-definable?) and searches for exact same pattern in the DNA of the other parent - if it finds a match, it switches over. If it does not - sticks with DNA from the same parent. If it finds several matches, then it picks one of them randomly.
This would solve the problem of sexual reproduction, it would also allow recombination that is command-oriented, not gene-oriented. The downside is that it still would not be possible to track evolution of whole genomes and build phylogenetic trees. But it would be a good start anyway. It actually would also allow turning off cross-species breeding - just set the "homology" level very high and it will never find exact match :)
Yeah, I kind of like that!
-
If it finds several matches, then it picks one of them randomly.
I was thinking of that too, but shouldn't distance from current location matter too?
That is, if there's a closer match you're more likely to use it than a match on the opposite side of the centromere.
-
More likely? Sure, why not...
Can you explain the whole centromere again or post a link? I am not 100% sure what you want to do there.
-
Here's the most recent post (http://s9.invisionfree.com/DarwinBots_Forum/index.php?showtopic=492&view=findpost&p=656549).
Any questions that doesn't answer (I don't remember all of what I said) go ahead and ask in that thread.
-
Sometimes you don't want it to be just a label. Say you want to compare fitness of two closely related organisms that reproduce sexually - then you don't want them to inter-breed.
Yes, this is true. But there should be a standard way to do that, instead of just making things work the wrong way because sometimes it is useful. Another way would be to simply program your creatures to ingoe each other as partners (risky) or mess up their dna - if they have ND execution, for example, you can completely invert the order of their genes without changing their functionality: and they will never be able to interbreed.
They are using the best software available and thier alignments usually take overnight and sometimes go for several days. Which makes me think that any program that does this in a fraction of a second is a sham.
It may be so. Or it may be that your colleagues work on much bigger data collections that we need to do. I don't think that aligning similar parts should be (nor that it can be) an error free procedure. It should only make things work better than they do now.
Basically, if you can do it - great! I won't complain. But I don't see why UID system can't be implemented - it is very powerful and yet it is very easy to add...
I prefer my system, which is not very different from yours except for the fact that
1) it doesn't need explicit and arbitrary marking of the code
2) it works _preferably_ (but not necessarily) on entire genes.
3) it's straightforward to implement
-
I vote on this (http://s9.invisionfree.com/DarwinBots_Forum/index.php?showtopic=557&view=findpost&p=709082) method with a slightly different order of actions. Instead of reading along and then deciding to cross over, you decide to cross over X times, pick a spot to try it at, if it fails pick a new spot, until you've succeeded X times or given up all together.
Then you copy the DNA and divide it into cells and reproduce. Minor point.
-
Nums, I also have to ask you if you can explain again for me the whole _chromosomes_ thing, or post a link. I can't find your original idea about chromosomes, and I'm not sure about how they should work.
-
Yeah, especially in the light of recent decision to go slightly undeterministic! I thought chromosomes were supposed to be slightly undeterministic in your previous idea.
What are we gonna use the chromosomes for?
-
Chromosomes are synchronous execution paths. They can't interfere with each other (although their commands may conflict), and appear from the bots point of view to be executing at the same time. Genes in the same chromosome operate more or less exactly how genes do now. Current bots can be seen as having a single chromosome. More chromosomes are like having multiple DNA files running in the same bot.
Chromosomes can combine to form pairs via centromeres. They lend themselves quite naturally to sexual reproduction, crossing over, and diploidness. They allow natural segregation of genes you don't want to be able to cross over with each other (crossing over restricted between like chromosomes only).
A few other things, I forget all the implications I worked out. If you really want a complete list, I'd have to dig through the old posts.