Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Look into converting sequences into bit strings #22

Open
ArtPoon opened this issue Jul 31, 2019 · 5 comments
Open

Look into converting sequences into bit strings #22

ArtPoon opened this issue Jul 31, 2019 · 5 comments

Comments

@ArtPoon
Copy link
Contributor

ArtPoon commented Jul 31, 2019

Two options:

  1. Encode nucleotides with two bits (four states = four nucleotides)
  2. Encode with four bits for presence/absence of each nucleotide, which enables us to encode mixtures (preferred).

Computing number of differences should be attainable by a fast bitwise operator.

kwade4 added a commit that referenced this issue Jul 31, 2019
-Implemented 'encode' (#22)
-Added unit test
-Fixes #19
@kwade4
Copy link
Collaborator

kwade4 commented Aug 7, 2019

The majority of the execution time is spent bootstrapping (eg: 151 seconds out of 164 seconds on Windows, using randint() ), so I am unsure whether using bit strings would provide much of a performance increase.

@ArtPoon
Copy link
Contributor Author

ArtPoon commented Aug 7, 2019

Ok but won't bootstrapping the match/mismatch binary vector instead of sequences speed things up considerably?

@ArtPoon
Copy link
Contributor Author

ArtPoon commented Aug 7, 2019

Also try replacing randint with random and round.

@kwade4
Copy link
Collaborator

kwade4 commented Aug 7, 2019

Yes, that would.
Regarding random and randint, I realized I misread the numbers. I updated my previous comment with the correct numbers.

Using randint: 151 of 164 seconds are spent bootstrapping (on Windows)
Using random and round: 47 of 52 seconds are spent bootstrapping (on Windows)

I also found using random.choices to pre-compute a list of random numbers, and slicing the list at each window could increase performance.

Using random.random() and round
n = len(best_seq)
for rep in range(nrep):
    boot = [best_seq[round(random.random() * (n - 1))] for _ in range(n)]
    if sum(boot) / len(boot) < second_p:
        count += 1
quant = count / nrep

Total Time = 52 seconds (on Windows)
Bootstrapping Tme = 47 seconds (on Windows)

Using random.choices()
n = len(best_seq)
sample = random.choices(best_seq, k=n*nrep)
for rep in range(nrep):
    boot = sample[rep: rep + n]
    if sum(boot) / n < second_p:
        count += 1
    quant = count / nrep

Total Time: 27 seconds (on Windows)
Bootstrapping Time: 23 seconds (on Windows)

@kwade4
Copy link
Collaborator

kwade4 commented Aug 7, 2019

I think using the match/mismatch binary vector and random.choices could speed things up (even on Windows).

kwade4 added a commit that referenced this issue Aug 28, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants