SLiQ

SLiQ predicts relative positions and orientations of contigs using simple linear inequalities derived from mate pair data to construct contig digraphs for scaffolding in de novo genome assembly.

Key Features:

• Simple linear inequalities: Uses inequalities derived from the geometric arrangement of contigs on a line to infer constraints from mate pair reads.
• Contig position and orientation prediction: Predicts relative positions and orientations of contigs based on individual mate pair reads.
• Contig digraph construction: Constructs a directed contig digraph representing inferred relationships between contigs.
• Mate-pair filtering: Filters out unreliable mate pairs to improve input data quality for scaffolding.
• Scaffolding algorithm: Implements a simple and efficient algorithm that generates linear scaffolds from the contig digraph.
• Validation and performance: Validated on datasets from bacterial genomes to mammalian genomes including human, showing high accuracy and outperforming majority voting procedures on larger genomes.

Scientific Applications:

• De novo genome scaffolding: Orders and orients contigs to produce scaffolds during de novo genome assembly using mate pair data.
• Preprocessing for scaffolding pipelines: Provides filtered mate-pair sets and contig digraphs as input for downstream scaffolding algorithms.
• Cross-taxa assembly: Applicable to assemblies ranging from bacterial genomes to complex mammalian genomes, including the human genome.

Methodology:

Derives simple linear inequalities from the geometric arrangement of contigs, applies these inequalities to individual mate pair reads to predict relative positions and orientations, filters unreliable mate pairs, constructs a directed contig digraph, and applies a simple scaffolding algorithm to generate linear scaffolds.