PS2 Q1B

[Orion]

Regarding question 1b, the handout says to find the "longest" chain.
Is this the chain that connects the most local alignments, the chain
that spans the longest distance, or the chain the spans the longest
distance within local alignments? I presume the last, but I wanted to
confirm.

Thanks,
Orion

[Michael Brudno]

It is the first -- the chain with the most local alignments.

[Orion Buske]

Thanks for putting up with all my questions. I have one more clarification, though. :)

Regarding problem 1.b, k is fixed, yes? So you've dropped all k terms from the asymptotic analysis...

Thanks,
-Orion

[Michael Brudno]

It is a parameter, but k << n. For the truly curious, the best known
algorithm is a little bit fastern than n log^k n. If you find that one
(or a similar one) without reading the papers you get a bonus. O(n^2)
is what I am expecting. You can assume that knlog n < n^2.

-M

[Brian]

Out of curiosity, is that:

n times log base k of n or
n times log log log ... k times.... log log n or
n times (log n)^k?

Regardless, that looks messy enough that I'm pretty sure I don't have
it.

On Nov 21, 9:09 pm, Michael Brudno <bru...@gmail.com> wrote:
> It is a parameter, but k << n. For the truly curious, the best known
> algorithm is a little bit fastern than n log^k n. If you find that one
> (or a similar one) without reading the papers you get a bonus. O(n^2)
> is what I am expecting. You can assume that knlog n < n^2.
>
> -M
>

> On Sun, Nov 21, 2010 at 6:37 PM, Orion Buske <orion.bu...@gmail.com> wrote:
> > Thanks for putting up with all my questions. I have one more clarification, though. :)
>
> > Regarding problem 1.b, k is fixed, yes? So you've dropped all k terms from the asymptotic analysis...
>
> > Thanks,
> > -Orion
>
> > On 21 Nov 2010, at 12:45 AM, Michael Brudno wrote:
>
> >> It is the first -- the chain with the most local alignments.
>

[Orion Buske]

Interesting, so their algorithm performs asymptotically faster the more sequences they align? That seems wrong...

[Michael Brudno]

the third.