Dataset Information

ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction.

ABSTRACT:

Motivation

The contig orientation problem, which we formally define as the MAX-DIR problem, has at times been addressed cursorily and at times using various heuristics. In setting forth a linear-time reduction from the MAX-CUT problem to the MAX-DIR problem, we prove the latter is NP-complete. We compare the relative performance of a novel greedy approach with several other heuristic solutions.

Results

Our results suggest that our greedy heuristic algorithm not only works well but also outperforms the other algorithms due to the nature of scaffold graphs. Our results also demonstrate a novel method for identifying inverted repeats and inversion variants, both of which contradict the basic single-orientation assumption. Such inversions have previously been noted as being difficult to detect and are directly involved in the genetic mechanisms of several diseases.

Availability and implementation

http://bioresearch.byu.edu/scaffoldscaffolder.

Contact

paulmbodily@gmail.com

Supplementary information

Supplementary data are available at Bioinformatics online.

SUBMITTER: Bodily PM

PROVIDER: S-EPMC5006237 | biostudies-literature | 2016 Jan

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction.

Bodily Paul M PM Fujimoto M Stanley MS Snell Quinn Q Ventura Dan D Clement Mark J MJ

Bioinformatics (Oxford, England) 20150917 1

<h4>Motivation</h4>The contig orientation problem, which we formally define as the MAX-DIR problem, has at times been addressed cursorily and at times using various heuristics. In setting forth a linear-time reduction from the MAX-CUT problem to the MAX-DIR problem, we prove the latter is NP-complete. We compare the relative performance of a novel greedy approach with several other heuristic solutions.<h4>Results</h4>Our results suggest that our greedy heuristic algorithm not only works well but ...[more]

PMID: 26382194

Similar Datasets

Project description:MotivationAdmixture, the interbreeding between previously distinct populations, is a pervasive force in evolution. The evolutionary history of populations in the presence of admixture can be modeled by augmenting phylogenetic trees with additional nodes that represent admixture events. While enabling a more faithful representation of evolutionary history, admixture graphs present formidable inferential challenges, and there is an increasing need for methods that are accurate, fully automated and computationally efficient. One key challenge arises from the size of the space of admixture graphs. Given that exhaustively evaluating all admixture graphs can be prohibitively expensive, heuristics have been developed to enable efficient search over this space. One heuristic, implemented in the popular method TreeMix, consists of adding edges to a starting tree while optimizing a suitable objective function.ResultsHere, we present a demographic model (with one admixed population incident to a leaf) where TreeMix and any other starting-tree-based maximum likelihood heuristic using its likelihood function is guaranteed to get stuck in a local optimum and return an incorrect network topology. To address this issue, we propose a new search strategy that we term maximum likelihood network orientation (MLNO). We augment TreeMix with an exhaustive search for an MLNO, referring to this approach as OrientAGraph. In evaluations including previously published admixture graphs, OrientAGraph outperformed TreeMix on 4/8 models (there are no differences in the other cases). Overall, OrientAGraph found graphs with higher likelihood scores and topological accuracy while remaining computationally efficient. Lastly, our study reveals several directions for improving maximum likelihood admixture graph estimation.Availability and implementationOrientAGraph is available on Github (https://github.com/sriramlab/OrientAGraph) under the GNU General Public License v3.0.Supplementary informationSupplementary data are available at Bioinformatics online.

Dataset Information

ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction.

Motivation

Results

Availability and implementation

Contact

Supplementary information

Publications

ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets