1 // ***************************************************************************
2 // bamtools_sort.cpp (c) 2010 Derek Barnett, Erik Garrison
3 // Marth Lab, Department of Biology, Boston College
4 // ---------------------------------------------------------------------------
5 // Last modified: 11 October 2011 (DB)
6 // ---------------------------------------------------------------------------
7 // Sorts an input BAM file
8 // ***************************************************************************
10 #include "bamtools_sort.h"
12 #include <api/SamConstants.h>
13 #include <api/BamMultiReader.h>
14 #include <api/BamWriter.h>
15 #include <api/algorithms/Sort.h>
16 #include <utils/bamtools_options.h>
17 using namespace BamTools;
18 using namespace BamTools::Algorithms;
32 // ** These defaults should be tweaked & 'optimized' per testing ** //
34 // I say 'optimized' because each system will naturally perform
35 // differently. We will attempt to determine a sensible
36 // compromise that should perform well on average.
37 const unsigned int SORT_DEFAULT_MAX_BUFFER_COUNT = 500000; // max numberOfAlignments for buffer
38 const unsigned int SORT_DEFAULT_MAX_BUFFER_MEMORY = 1024; // Mb
40 } // namespace BamTools
42 // ---------------------------------------------
43 // SortSettings implementation
45 struct SortTool::SortSettings {
48 bool HasInputBamFilename;
49 bool HasMaxBufferCount;
50 bool HasMaxBufferMemory;
51 bool HasOutputBamFilename;
55 string InputBamFilename;
56 string OutputBamFilename;
59 unsigned int MaxBufferCount;
60 unsigned int MaxBufferMemory;
64 : HasInputBamFilename(false)
65 , HasMaxBufferCount(false)
66 , HasMaxBufferMemory(false)
67 , HasOutputBamFilename(false)
68 , IsSortingByName(false)
69 , InputBamFilename(Options::StandardIn())
70 , OutputBamFilename(Options::StandardOut())
71 , MaxBufferCount(SORT_DEFAULT_MAX_BUFFER_COUNT)
72 , MaxBufferMemory(SORT_DEFAULT_MAX_BUFFER_MEMORY)
76 // ---------------------------------------------
77 // SortToolPrivate implementation
79 class SortTool::SortToolPrivate {
83 SortToolPrivate(SortTool::SortSettings* settings);
84 ~SortToolPrivate(void) { }
92 bool CreateSortedTempFile(vector<BamAlignment>& buffer);
93 bool GenerateSortedRuns(void);
94 bool MergeSortedRuns(void);
95 bool WriteTempFile(const vector<BamAlignment>& buffer, const string& tempFilename);
96 void SortBuffer(vector<BamAlignment>& buffer);
100 SortTool::SortSettings* m_settings;
101 string m_tempFilenameStub;
104 RefVector m_references;
105 vector<string> m_tempFilenames;
109 SortTool::SortToolPrivate::SortToolPrivate(SortTool::SortSettings* settings)
110 : m_settings(settings)
113 // set filename stub depending on inputfile path
114 // that way multiple sort runs don't trip on each other's temp files
116 size_t extensionFound = m_settings->InputBamFilename.find(".bam");
117 if ( extensionFound != string::npos )
118 m_tempFilenameStub = m_settings->InputBamFilename.substr(0,extensionFound);
119 m_tempFilenameStub.append(".sort.temp.");
123 // generates mutiple sorted temp BAM files from single unsorted BAM file
124 bool SortTool::SortToolPrivate::GenerateSortedRuns(void) {
126 // open input BAM file
128 if ( !reader.Open(m_settings->InputBamFilename) ) {
129 cerr << "bamtools sort ERROR: could not open " << m_settings->InputBamFilename
130 << " for reading... Aborting." << endl;
134 // get basic data that will be shared by all temp/output files
135 SamHeader header = reader.GetHeader();
136 header.SortOrder = ( m_settings->IsSortingByName
137 ? Constants::SAM_HD_SORTORDER_QUERYNAME
138 : Constants::SAM_HD_SORTORDER_COORDINATE );
139 m_headerText = header.ToString();
140 m_references = reader.GetReferenceData();
142 // set up alignments buffer
144 vector<BamAlignment> buffer;
145 buffer.reserve( (size_t)(m_settings->MaxBufferCount*1.1) );
146 bool bufferFull = false;
148 // if sorting by name, we need to generate full char data
149 // so can't use GetNextAlignmentCore()
150 if ( m_settings->IsSortingByName ) {
152 // iterate through file
153 while ( reader.GetNextAlignment(al)) {
155 // check buffer's usage
156 bufferFull = ( buffer.size() >= m_settings->MaxBufferCount );
158 // store alignments until buffer is "full"
160 buffer.push_back(al);
162 // if buffer is "full"
164 // so create a sorted temp file with current buffer contents
165 // then push "al" into fresh buffer
166 CreateSortedTempFile(buffer);
167 buffer.push_back(al);
172 // sorting by position, can take advantage of GNACore() speedup
175 // iterate through file
176 while ( reader.GetNextAlignmentCore(al) ) {
178 // check buffer's usage
179 bufferFull = ( buffer.size() >= m_settings->MaxBufferCount );
181 // store alignments until buffer is "full"
183 buffer.push_back(al);
185 // if buffer is "full"
187 // create a sorted temp file with current buffer contents
188 // then push "al" into fresh buffer
189 CreateSortedTempFile(buffer);
190 buffer.push_back(al);
195 // handle any leftover buffer contents
196 if ( !buffer.empty() )
197 CreateSortedTempFile(buffer);
199 // close reader & return success
204 bool SortTool::SortToolPrivate::CreateSortedTempFile(vector<BamAlignment>& buffer) {
209 // write sorted contents to temp file, store success/fail
210 stringstream tempStr;
211 tempStr << m_tempFilenameStub << m_numberOfRuns;
212 bool success = WriteTempFile( buffer, tempStr.str() );
214 // save temp filename for merging later
215 m_tempFilenames.push_back(tempStr.str());
217 // clear buffer contents & update run counter
221 // return success/fail of writing to temp file
222 // TODO: a failure returned here is not actually caught and handled anywhere
226 // merges sorted temp BAM files into single sorted output BAM file
227 bool SortTool::SortToolPrivate::MergeSortedRuns(void) {
229 // open up multi reader for all of our temp files
230 // this might get broken up if we do a multi-pass system later ??
231 BamMultiReader multiReader;
232 if ( !multiReader.Open(m_tempFilenames) ) {
233 cerr << "bamtools sort ERROR: could not open BamMultiReader for merging temp files... Aborting."
238 // open writer for our completely sorted output BAM file
239 BamWriter mergedWriter;
240 if ( !mergedWriter.Open(m_settings->OutputBamFilename, m_headerText, m_references) ) {
241 cerr << "bamtools sort ERROR: could not open " << m_settings->OutputBamFilename
242 << " for writing... Aborting." << endl;
247 // while data available in temp files
249 while ( multiReader.GetNextAlignmentCore(al) )
250 mergedWriter.SaveAlignment(al);
254 mergedWriter.Close();
256 // delete all temp files
257 vector<string>::const_iterator tempIter = m_tempFilenames.begin();
258 vector<string>::const_iterator tempEnd = m_tempFilenames.end();
259 for ( ; tempIter != tempEnd; ++tempIter ) {
260 const string& tempFilename = (*tempIter);
261 remove(tempFilename.c_str());
268 bool SortTool::SortToolPrivate::Run(void) {
270 // this does a single pass, chunking up the input file into smaller sorted temp files,
271 // then write out using BamMultiReader to handle merging
273 if ( GenerateSortedRuns() )
274 return MergeSortedRuns();
279 void SortTool::SortToolPrivate::SortBuffer(vector<BamAlignment>& buffer) {
281 // ** add further custom sort options later ?? **
283 // sort buffer by desired method
284 if ( m_settings->IsSortingByName )
285 std::stable_sort( buffer.begin(), buffer.end(), Sort::ByName() );
287 std::stable_sort( buffer.begin(), buffer.end(), Sort::ByPosition() );
290 bool SortTool::SortToolPrivate::WriteTempFile(const vector<BamAlignment>& buffer,
291 const string& tempFilename)
293 // open temp file for writing
294 BamWriter tempWriter;
295 if ( !tempWriter.Open(tempFilename, m_headerText, m_references) ) {
296 cerr << "bamtools sort ERROR: could not open " << tempFilename
297 << " for writing." << endl;
302 vector<BamAlignment>::const_iterator buffIter = buffer.begin();
303 vector<BamAlignment>::const_iterator buffEnd = buffer.end();
304 for ( ; buffIter != buffEnd; ++buffIter ) {
305 const BamAlignment& al = (*buffIter);
306 tempWriter.SaveAlignment(al);
309 // close temp file & return success
314 // ---------------------------------------------
315 // SortTool implementation
317 SortTool::SortTool(void)
319 , m_settings(new SortSettings)
322 // set program details
323 Options::SetProgramInfo("bamtools sort", "sorts a BAM file", "[-in <filename>] [-out <filename>] [sortOptions]");
326 OptionGroup* IO_Opts = Options::CreateOptionGroup("Input & Output");
327 Options::AddValueOption("-in", "BAM filename", "the input BAM file", "",
328 m_settings->HasInputBamFilename, m_settings->InputBamFilename,
329 IO_Opts, Options::StandardIn());
330 Options::AddValueOption("-out", "BAM filename", "the output BAM file", "",
331 m_settings->HasOutputBamFilename, m_settings->OutputBamFilename,
332 IO_Opts, Options::StandardOut());
334 OptionGroup* SortOpts = Options::CreateOptionGroup("Sorting Methods");
335 Options::AddOption("-byname", "sort by alignment name", m_settings->IsSortingByName, SortOpts);
337 OptionGroup* MemOpts = Options::CreateOptionGroup("Memory Settings");
338 Options::AddValueOption("-n", "count", "max number of alignments per tempfile", "",
339 m_settings->HasMaxBufferCount, m_settings->MaxBufferCount,
340 MemOpts, SORT_DEFAULT_MAX_BUFFER_COUNT);
341 Options::AddValueOption("-mem", "Mb", "max memory to use", "",
342 m_settings->HasMaxBufferMemory, m_settings->MaxBufferMemory,
343 MemOpts, SORT_DEFAULT_MAX_BUFFER_MEMORY);
346 SortTool::~SortTool(void) {
355 int SortTool::Help(void) {
356 Options::DisplayHelp();
360 int SortTool::Run(int argc, char* argv[]) {
362 // parse command line arguments
363 Options::Parse(argc, argv, 1);
365 // initialize SortTool with settings
366 m_impl = new SortToolPrivate(m_settings);
368 // run SortTool, return success/fail