Re: [Seqan-dev] Time complexity of posGlobalize

["Weese, David" <weese@campus.fu-berlin.de>]

Hi John,

you will find an introduction to the two position types for multiple sequences in the tutorial:

http://trac.mi.fu-berlin.de/seqan/wiki/Tutorial/Indices#HandlingMultipleSequences

There is a link to the metafunction SAValue which can be overloaded to change the position type used by an index:

http://www.seqan.de/dddoc/html_devel/METAFUNCTION_S_A_Value.html

The ESA index Index<TText, IndexEsa<> > as well as most of the subclasses that whose a TSpec argument is Foo<> (and not Foo) can be further specialized in the form Foo<MoreSpecial<> > and Foo<MoreSpecial<EvenMoreSpecial<> > > and so on. That leaves room for further enhancements or specializations like a custom SAValue.

struct MyIndex;

template <typename TText>

struct SAValue<Index<TText, IndexEsa<MyIndex> > >

{

typedef Pair<unsigned, unsigned, BitCompressed<19,13> > Type;

};

Would it have helped if that was a part of the tutorial? Or where would you search for that example?

Regards,

David
--
David Weese weese@inf.fu-berlin.de
Freie Universität Berlin http://www.inf.fu-berlin.de/
Institut für Informatik Phone: +49 30 838 75246
Takustraße 9 Algorithmic Bioinformatics
14195 Berlin Room 021 

Am 27.07.2011 um 14:19 schrieb John Reid:

On 27/07/11 12:31, John Reid wrote:

On 26/07/11 07:17, Weese, David wrote:

Hi John,

posGlobalize needs in either case constant time. posLocalize takes

constant time only for pairs. Otherwise (for global positions =

integers) it takes O(m log m) where m is the number of sequences.

And yes, global positions help to save memory. But you can configure

the type used in the position tables by overloading SAValue for your

index. With Packed Pairs you specify the number of bits used for

seqno and seqofs.

That sounds interesting. I'm not quite sure where in the documentation

I should look to see what how I should overload SAValue. Is there

documentation on this?

I think I worked it out by trial and error:

Index< string_set_t, IndexEsa< Pair< unsigned int, unsigned int,
BitCompressed< 17, 13 > > > >

seems to be doing the job. I would like to know if it is just that I
don't understand how the docs work or whether it is missing from the
docs. Quite often I can't find things in the docs.

_______________________________________________
seqan-dev mailing list
seqan-dev@lists.fu-berlin.de
https://lists.fu-berlin.de/listinfo/seqan-dev