FU Logo
  • Startseite
  • Kontakt
  • Impressum
  • Home
  • Listenauswahl
  • Anleitungen

Re: [Seqan-dev] Time complexity of posGlobalize

<-- thread -->
<-- date -->
  • From: "Weese, David" <weese@campus.fu-berlin.de>
  • To: SeqAn Development <seqan-dev@lists.fu-berlin.de>
  • Date: Tue, 26 Jul 2011 08:17:22 +0200
  • Acceptlanguage: de-DE
  • Reply-to: SeqAn Development <seqan-dev@lists.fu-berlin.de>
  • Subject: Re: [Seqan-dev] Time complexity of posGlobalize

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.

HTH
David

Sent from my iPod. Sorry for being short.

Am 25.07.2011 um 11:49 schrieb "John Reid" <j.reid@mail.cryst.bbk.ac.uk>:

> Suppose I have an iterator over a suffix array. What is the time 
> complexity of calling posGlobalise() on an occurrence the iterator? I'm 
> asking because I have the option to store indexes to occurrences as 
> global positions or as local positions (pairs of sequence ids, position 
> in sequences). I'm guessing the latter is more time efficient but would 
> take more storage.
> 
> Thanks,
> John.
> 
> _______________________________________________
> seqan-dev mailing list
> seqan-dev@lists.fu-berlin.de
> https://lists.fu-berlin.de/listinfo/seqan-dev



<-- thread -->
<-- date -->
  • Follow-Ups:
    • Re: [Seqan-dev] Time complexity of posGlobalize
      • From: "Weese, David" <weese@campus.fu-berlin.de>
    • Re: [Seqan-dev] Time complexity of posGlobalize
      • From: John Reid <j.reid@mail.cryst.bbk.ac.uk>
  • References:
    • [Seqan-dev] Time complexity of posGlobalize
      • From: John Reid <j.reid@mail.cryst.bbk.ac.uk>
  • seqan-dev - July 2011 - Archives indexes sorted by:
    [ thread ] [ subject ] [ author ] [ date ]
  • Complete archive of the seqan-dev mailing list
  • More info on this list...

Hilfe

  • FAQ
  • Dienstbeschreibung
  • ZEDAT Beratung
  • postmaster@lists.fu-berlin.de

Service-Navigation

  • Startseite
  • Listenauswahl

Einrichtung Mailingliste

  • ZEDAT-Portal
  • Mailinglisten Portal