pezmaster31/bamtools — Issue #37: Pileup can be very slow in High Copy number regions
Author: colinhercus
Created: 2012-03-08 03:27:44+00:00
State: open

I noticed that pileup became very slow when it gets into high copy number regions.

I tracked this down to ClearOldData() and the use of the erase method to remove alignments.
The modified routine below does away with erase and instead packs the elements up and then resizes the vector. This has improved performance dramatically but may still not be the optimum solution. Replacing the vector by a linked list collection might be even faster as you could then use erase() and the alignments wouldn't need to be repacked but I didn't have time to check other repercussions of this and so didn't try it.

The modified routine is:

```
void PileupEngine::PileupEnginePrivate::(void) {

// remove any data that ends before CurrentPosition
size_t i = 0, j = 0;
while ( i < CurrentAlignments.size() ) {

// remove alignment if it ends before CurrentPosition
const int endPosition = CurrentAlignments[i].GetEndPosition();
if ( endPosition <= CurrentPosition ) {
i++;
continue;
}
if(i != j)
CurrentAlignments[j] = CurrentAlignments[i];
i++;
j++;
}
CurrentAlignments.resize(j);
}
```
Kind Regards, Colin