Need help/hints on programming HW

[hans030390]

On my latest assignment, I'm stuck with two problems:


1. DNA is sampled in small fragments, which are then glued together into a longer strand. Define a procedure fuse-fragments which takes two DNA sequences, seq1 and seq2, locates the area of overlap, and returns the result of joining the two sequences together. The overlap area is the longest suffix of seq1 that matches a prefix of seq2 and it only appears once in the resulting sequence. Hint: use the prefix? procedure that you defined in the previous problem.
> (fuse-fragments '(a a a t t t t) '(t t t t g g g g g))
(a a a t t t t g g g g g)
> (fuse-fragments '(a a a) '(g g g))
(a a a g g g)
> (fuse-fragments '(a t t a) '(t t a a))
(a t t a a)

This is what I defined prefix as:

; prefix? takes two lists and returns #t if the first list is a prefix of the
; second list, and #f otherwise

(define prefix?
(lambda (ls1 ls2)
(if (null? ls1)
#t
(if (equal? (car ls1) (car ls2))
(prefix? (cdr ls1) (cdr ls2))
#f))))

And the next problem:


2. In a highly simplified model of reproduction, the DNA from two parents is combined to form the DNA of the offspring. In a process called crossover, corresponding chunks of the parent's DNA are exchanged. The following diagram illustrates what happens when there is just one crossover point.

Define a procedure crossover that takes two DNA sequences and a single crossover point (i.e., a number indicating where the transition occurs), and returns the DNA for the offspring. You may assume that both parent sequences are the same length, say n, and the crossover point is an integer in the range 1 to n -1, inclusive.
> (crossover '(a c t) '(t g g) 2)
(a c g)
> (crossover '(a a a a a a a a a a) '(t t t t t t t t t t) 4)
(a a a a t t t t t t)
> (crossover
'(t t t t t t t t t t t t t)
'(a a a a a a a a a a a a a)
8)
(t t t t t t t t a a a a a)

Any hints or help? I'd greatly appreciate it.

 

[dinkumthinkum]

From a cursory glance, your prefix function looks like it is missing a case for when ls2 is shorter than ls1.

For the fuse-fragments function, try writing a simple function called "tails" which returns a list of successive applications of "cdr" to a list (so it will return a list of lists). For example:

(tails '(1 2 3)) => ((1 2 3) (2 3) (3) ())

I hope you can see how this can be useful in combination with prefix?

For the second problem, think about how "append" works, but instead of appending elements to the list, choose from one or the other list based on the value of n.

 

[hans030390]

Originally posted by: dinkumthinkum
From a cursory glance, your prefix function looks like it is missing a case for when ls2 is shorter than ls1.

For the fuse-fragments function, try writing a simple function called "tails" which returns a list of successive applications of "cdr" to a list (so it will return a list of lists). For example:

(tails '(1 2 3)) => ((1 2 3) (2 3) (3) ())

I hope you can see how this can be useful in combination with prefix?

For the second problem, think about how "append" works, but instead of appending elements to the list, choose from one or the other list based on the value of n.

With my test cases, I still get the correct result if ls2 is shorter than ls1.

I'm not sure what "append" is. I don't think we've covered that. If that's the case, I can't use it.

Edit: Oops, I didn't notice you said append was for the 2nd problem. I just figured that one out.

Edit 2: Yup, guess my prefix? needs work. The autograder said it failed one or more cases.

 

[dinkumthinkum]

append is a basic function which appends two lists. I can't imagine how you have not covered it. It's the function you learn after "list".

Also I didn't tell you to USE it. I told you think about how it works, and work from there.

 

[hans030390]

Ok, so...if the car of tails is a prefix of ls2, then you want to add that into a list...and recur...? That's about as far as my brain gets...any attempts to do anything on the computer doesn't work out for me. I'm really stuck on this one.

 

[hans030390]

Originally posted by: dinkumthinkum
append is a basic function which appends two lists. I can't imagine how you have not covered it. It's the function you learn after "list".

Also I didn't tell you to USE it. I told you think about how it works, and work from there.

We probably did, then. I forget a lot of stuff in there pretty easily if we don't use it much.

Oh well, I figured it out anyway. I'm just super stuck with that fuse problem.

 

[dinkumthinkum]

Tails returns suffices in order of largest to smallest, right? So wouldn't the first matching one be ok?

 

[hans030390]

Right, I understand that part...I really have no idea where I'm stuck at with this one.

 

[hans030390]

I've (somehow) made a little bit of progress...I've gotten to the point where I can get the following:

> (fuse-fragments '(a a) '(a a g f d f))
(a a g f d f)

So, that's right...but:

> (fuse-fragments '(a a t) '(a a g))
(a a t)

I'm close(r)...what's this last thing I'm missing? Here's my code so far...perhaps it's completely off, yet it manages to "sort of" work. Where to go from here?

(define fuse-fragments
(lambda (ls1 ls2)
(if (null? ls1)
ls2
(if (null? ls2)
ls1
(if (prefix? ls1 ls2)
ls2
(cons (car ls1) (fuse-fragments (cdr ls1) (cdr ls2))))))))

Edit: I guess it doesn't like the indentation used in the code, so it put it all up against the left side. Hopefully that's not a problem.

 

[dinkumthinkum]

NP. Emacs can reindent it automatically.

I would say the problem is that you are traversing both lists simultaneously. Wouldn't you only want to traverse the first list?

NB: also if you are nesting 'if' expressions like that you should be using 'cond' instead.

 

[hans030390]

Ok, I forgot to mention that I got it figured out (via help from office hours). It was way simpler than I thought it would end up being (no helper needed, like "tails"). Thanks for your help, though.