Abstract
Next generation sequencing technologies have allowed us to efficiently produce draft genomes for many organisms of interest. However, most draft genomes are just col-lections of independent contigs, whose relative positions and orientations along the genome being sequenced are unknown. Scaffolding is a process to determine the or-ders and orientations of these contigs, which is critical and helpful for accomplishing the subsequent finishing process. Currently, several tools have been developed to or-der and orient the contigs of draft genomes using single reference genome. However, most of these tools can apply only on a complete reference genome. This may reduce the usability in practice since, the availability of draft genomes greatly exceeds that of completely sequenced ones in current public databases. Several tools have been developed to address this problem, including CSAR proposed by our laboratory that can order and orient the contigs in target genome by using a draft reference genome. However, all these single-reference based tools may produce erroneous scaffolds of draft genomes if there is rearrangement distance between the target genome and the reference genome. Ragout and MeDuSa are two recently developed scaffolding tools using multiple complete or draft reference genomes. Note that Ragout requires the user to input a phylogenetic tree of the target and reference genomes, which actually cannot be easily obtained by the user in advance. In this study, we present a scaf-folding tool called Multi-CSAR that can utilize multiple complete or draft reference genomes to produce high-quality scaffolds of draft genomes. Like MeDuSa, our Multi-CSAR does not require prior knowledge on the evolutionary relationships among the target and reference genomes. Moreover, in contrast to Ragout and Me-DuSa, both attempting to solve NP-hard problem, the algorithm behind our Mul-ti-CSAR involves only polynomial time solvable problems. Finally, we have tested our Multi-CSAR on the real and simulated datasets and compared its results with those obtained by Ragout and MeDuSa. Our experimental results have shown that Multi-CSAR indeed outperforms Ragout and MeDuSa in terms of many metrics such as sensitivity, precision, F-score, genome coverage, scaffold number and scaffold N50 size.