SLIQ: Simple Linear Inequalities for Efficient Contig Scaffolding

Details SLIQ: Simple Linear Inequalities for Efficient Contig Scaffolding SLIQ: Simple Linear Inequalities for Efficient Contig Scaffolding

2011-11-06

arxiv.org/abs/1111.1426v2

Biology

Quantitative Biology

Genomics

16 pages, 6 figures, 7 tables

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

SLIQ: Simple Linear Inequalities for Efficient Contig Scaffolding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with SLIQ: Simple Linear Inequalities for Efficient Contig Scaffolding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and SLIQ: Simple Linear Inequalities for Efficient Contig Scaffolding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-704743