SLIQ: simple linear inequalities for efficient contig scaffolding.

Scaffolding is an important subproblem in de novo genome assembly, in which mate pair data are used to construct a linear sequence of contigs separated by gaps. Here we present SLIQ, a set of simple linear inequalities derived from the geometry of contigs on the line that can be used to predict the relative positions and orientations of contigs from individual mate pair reads and thus produce a contig digraph. The SLIQ inequalities can also filter out unreliable mate pairs and can be used as a preprocessing step for any scaffolding algorithm. We tested the SLIQ inequalities on five real data sets ranging in complexity from simple bacterial genomes to complex mammalian genomes and compared the results to the majority voting procedure used by many other scaffolding algorithms. SLIQ predicted the relative positions and orientations of the contigs with high accuracy in all cases and gave more accurate position predictions than majority voting for complex genomes, in particular the human genome. Finally, we present a simple scaffolding algorithm that produces linear scaffolds given a contig digraph. We show that our algorithm is very efficient compared to other scaffolding algorithms while maintaining high accuracy in predicting both contig positions and orientations for real data sets.

Roy RS ，Chen KC ，Sengupta AM ，Schliep A ... -  《-》

Multi-CAR: a tool of contig scaffolding using multiple references.

Chen KT ，Chen CJ ，Shen HT ，Liu CL ，Huang SH ，Lu CL ... -  《BMC BIOINFORMATICS》

CAR: contig assembly of prokaryotic draft genomes using rearrangements.

Lu CL ，Chen KT ，Huang SY ，Chiu HT ... -  《BMC BIOINFORMATICS》

A tool for analyzing mate pairs in assemblies (TAMPA).

The current generation of genome assembly programs uses distance and orientation relationships of paired end reads of clones (mate pairs) to order and orient contigs. Mate pair data can also be used to evaluate and compare assemblies after the fact. Earlier work employed a simple heuristic to detect assembly problems by scanning across an assembly to locate peak concentrations of unsatisfied mate pairs. TAMPA is a novel, computational geometry-based approach to detecting assembly breakpoints by exploiting constraints that mate pairs impose on each other. The method can be used to improve assemblies and determine which of two assemblies is correct in the case of sequence disagreement. Results from several human genome assemblies are presented.

Dew IM ，Walenz B ，Sutton G 《JOURNAL OF COMPUTATIONAL BIOLOGY》

Heterozygous genome assembly via binary classification of homologous sequence.

Bodily PM ，Fujimoto M ，Ortega C ，Okuda N ，Price JC ，Clement MJ ，Snell Q ... -  《BMC BIOINFORMATICS》