title: BOSS: a novel scaffolding algorithm based on an optimized scaffold graph.
abstract: While aiming to determine orientations and orders of fragmented contigs, scaffolding is an essential step of assembly pipelines and can make assembly results more complete. Most existing scaffolding tools adopt scaffold graph approaches. However, due to repetitive regions in genome, sequencing errors and uneven sequencing depth, constructing an accurate scaffold graph is still a challenge task.
  
  
  
  In this paper, we present a novel algorithm (called BOSS), which employs paired reads for scaffolding. To construct a scaffold graph, BOSS utilizes the distribution of insert size to decide whether an edge between two vertices (contigs) should be added and how an edge should be weighed. Moreover, BOSS adopts an iterative strategy to detect spurious edges whose removal can guarantee no contradictions in the scaffold graph. Based on the scaffold graph constructed, BOSS employs a heuristic algorithm to sort vertices (contigs) and then generates scaffolds. The experimental results demonstrate that BOSS produces more satisfactory scaffolds, compared with other popular scaffolding tools on real sequencing data of four genomes.
  
  
  
  BOSS is publicly available for download at https://github.com/bioinfomaticsCSU/BOSS CONTACT: jxwang@mail.csu.edu.cnSupplementary information: Supplementary data are available at Bioinformatics online.
authors.affiliation: School of Information Science and Engineering, Central South University, ChangSha 410083, China.|College of Computer Science and Technology, Henan Polytechnic University, JiaoZuo 454000, China.
authors.forename: Junwei
authors.initials: J
authors.lastname: Luo
authors.affiliation: School of Information Science and Engineering, Central South University, ChangSha 410083, China.
authors.forename: Jianxin
authors.initials: J
authors.lastname: Wang
authors.affiliation: School of Information Science and Engineering, Central South University, ChangSha 410083, China.
authors.forename: Zhen
authors.initials: Z
authors.lastname: Zhang
authors.affiliation: School of Information Science and Engineering, Central South University, ChangSha 410083, China.
authors.forename: Min
authors.initials: M
authors.lastname: Li
authors.affiliation: Division of Biomedical Engineering, University of Saskatchewan, Saskatchewan S7N 5A9, Canada.
authors.forename: Fang-Xiang
authors.initials: FX
authors.lastname: Wu
mesh_terms: D000465:Algorithms; D016678:Genome; D006801:Humans; D010963:Plasmodium falciparum / Q000235:genetics; D012091:Repetitive Sequences, Nucleic Acid; D012242:Rhodobacter sphaeroides / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software; D013211:Staphylococcus aureus / Q000235:genetics