1
$\begingroup$

In genetics and breeding, we typically have two parent genotype (may or may not be the same) which can produce a set of offspring with certain probability (assuming simple Mendelian inheritance).

I am looking for a way to determine given a set of parent, what is the shortest path to a particular offspring genotype (and yes, I am talking about breeding flowers in Animal Crossing!).

This seems to be very similar to the shortest path problem, but now the edges is given by two nodes interacting with each other. Is there a way to achieve this?

I was directed to here from stack overflow. My original post was at stackoverflow.

Edit: A genotype is a word of four groups of two chars. These groups can be xx, Xx or XX where x = {r,b,y,w}. For example; RRbbyyWw is a red flower.

An offspring of two parents inherits a random combination of letters. For example, if parent A has genotype RRbbyyWw and parent B has genotype rrBBYyww then the offspring might be RRBbyyWw.

If, by luck, the offspring has inherited rRBbyyWw (rR is not allowed) then it is reordered so it becomes RrBbyyWw.

Now, the question is; given genotypes of a set of parents and a target genotype, is there an algorithm which can generate the shortest path in terms of pairing parents?

Edit2: I am aware of the data mining done by others (e.g. here and here.) Therefore, I am not looking for a particular path to get to certain result, rather a method to find a (shortest) path.

Improve this question
$\endgroup$
5
  • $\begingroup$ This sounds like an interesting problem. But to get to developing an optimization algorithm for it we need to describe it mathematically first. Is genotype basically a sequence of letters G,A,C,T? How long is the sequence in this case? What are the rules for offspring genotype, given two parents' genotypes? Some (or perhaps all) elements in the offspring genotype inherit their values from one or the other parent with a certain probability? What is the probability? Is there distinction male vs. female parent? $\endgroup$
    – Maxim Umansky
    Jun 2, 2020 at 21:56
  • $\begingroup$ @MaximUmansky Ian's particular problem -flower breeding in Animal Crossing- is datamined from the game's code and rewritten here gist.github.com/Treeki/7297a459bb104ae5401c1ce5f7e205a6 . It seems to me that gene set is a little bit larger than 4 letters but in the end it is a set of letters. $\endgroup$
    – Abdullah Ali Sivas
    Jun 3, 2020 at 22:14
  • $\begingroup$ I just found this friendlier write-up. docs.google.com/document/d/… $\endgroup$
    – Abdullah Ali Sivas
    Jun 3, 2020 at 22:25
  • $\begingroup$ It sounds like many people know this problem. I thought it came from an actual research project. Is this problem from an online game of some kind? Or from an online problem-solving competition? $\endgroup$
    – Maxim Umansky
    Jun 3, 2020 at 23:47
  • $\begingroup$ I don't think it is a known problem, it is an interesting one though. Animal Crossing is a Switch game (a Nintendo company product) where you manage and foster an island community, but that is not really related to the mathematics of the posed problem. I guess a good tag would be "recreational mathematics", though. I am suggesting an edit to Ian's question now. $\endgroup$
    – Abdullah Ali Sivas
    Jun 4, 2020 at 3:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.