FinIS: Improved in silico finishing using an exact quadratic programming formulation

Song Gao, Denis Bertrand, Niranjan Nagarajan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

22 Citations (Scopus)

Abstract

With the increased democratization of sequencing, the reliance of sequence assembly programs on heuristics is at odds with the need for black-box assembly solutions that can be used reliably by non-specialists. In this work, we present a formal definition for in silico assembly validation and finishing and explore the feasibility of an exact solution for this problem using quadratic programming (FinIS). Based on results for several real and simulated datasets, we demonstrate that FinIS validates the correctness of a larger fraction of the assembly than existing ad hoc tools. Using a test for unique optimal solutions, we show that FinIS can improve on both precision and recall values for the correctness of assembled sequences, when compared to competing programs. Source code and executables for FinIS are freely available at http://sourceforge.net/ projects/finis/.

Original languageEnglish
Title of host publicationAlgorithms in Bioinformatics - 12th International Workshop, WABI 2012, Proceedings
Pages314-325
Number of pages12
DOIs
Publication statusPublished or Issued - 2012
Externally publishedYes
Event12th International Workshop on Algorithms in Bioinformatics, WABI 2012 - Ljubljana, Slovenia
Duration: 10 Sept 201212 Sept 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7534 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Workshop on Algorithms in Bioinformatics, WABI 2012
Country/TerritorySlovenia
CityLjubljana
Period10/09/1212/09/12

Keywords

  • Finishing
  • Genome Assembly
  • Graph Algorithms
  • Quadratic Programming

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Cite this