1 Genome Analysis A Fast Hybrid Short Read Fragment Assembly Algorithm

Summary: The shorter and vastly more numerous reads produced by second-generation sequencing technologies require new tools that can assemble massive numbers of reads in reasonable time. Existing short-read assembly tools can be classified into two catego-ries: greedy extension-based and graph-based. While the graph-based approaches are generally superior in terms of assembly qual-ity, the computer resources required for building and storing a huge graph are very high. In this paper, we present Taipan, an assembly algorithm which can be viewed as a hybrid of these two approaches. Taipan uses greedy extensions for contig construction but at each step realizes enough of the corresponding read graph to make bet-ter decisions as to how assembly should continue. We show that this approach can achieve an assembly quality at least as good as the graph-based approaches used in the popular Edena and Velvet assembly tools using a moderate amount of computing resources. Availability and Implementation: Source code in C running on Linux is freely available a