Sequence Alignment on Directed Graphs
Preprint
Abstract
Genomic variations in a reference collection are naturally represented as genome variation graphs. Such graphs encode common subsequences as vertices and the variations are captured using additional vertices and directed edges. The resulting graphs are directed graphs possibly with cycles. Existing algorithms for aligning sequences on such graphs make use of partial order alignment (POA) techniques that work on directed acyclic graphs (DAG). For this, acyclic extensions of the input graphs are first constructed through expensive loop unrolling steps (DAGification). Also, such graph extensions could have considerable blow up in their size and in the worst case the blow up factor is proportional to the input sequence length. We provide a novel alignment algorithm V-ALIGN that aligns the input sequence directly on the input graph while avoiding such expensive DAGification steps. V-ALIGN is based on a novel dynamic programming formulation that allows gapped alignment directly on the input graph. It supports affine and linear gaps. We also propose refinements to V-ALIGN for better performance in practice. In this, the time to fill the DP table has linear dependence on the sizes of the sequence, the graph and its feedback vertex set. We perform experiments to compare against the POA based alignment. For aligning short sequences, standard approaches restrict the expensive gapped alignment to small filtered subgraphs having high ‘similarity’ to the input sequence. In such cases, the performance of V-ALIGN for gapped alignment on the filtered subgraph depends on the subgraph sizes.Keywords
All Related Versions
- Published version: Journal of Computational Biology, 26 (1), 53.
This publication has 16 references indexed in Scilit:
- Computational pan-genomics: status, promises and challengesBriefings in Bioinformatics, 2016
- Improved genome inference in the MHC using a population reference graphNature Genetics, 2015
- How to apply de Bruijn graphs to genome assemblyNature Biotechnology, 2011
- Cactus: Algorithms for genome multiple sequence alignmentGenome Research, 2011
- Cactus Graphs for Genome ComparisonsJournal of Computational Biology, 2011
- Enredo and Pecan: Genome-wide mammalian consistency-based multiple alignment with paralogsGenome Research, 2008
- The fragment assembly string graphBioinformatics, 2005
- De Novo Repeat Classification and Fragment AssemblyGenome Research, 2004
- Initial sequencing and analysis of the human genomeNature, 2001
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981