Limits...
Genome alignment with graph data structures: a comparison.

Kehr B, Trappe K, Holtgrewe M, Reinert K - BMC Bioinformatics (2014)

Bottom Line: We show that crucial pieces of alignment information, associated with inversions and duplications, are not visible in the structure of all graphs.Still, many ideas are shared among all graph-based approaches.Based on these findings, we outline a conceptual framework for graph-based genome alignment that can assist in the development of future genome alignment tools.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science, Freie Universität Berlin, Takustr, 9, 14195 Berlin, Germany. birte.kehr@fu-berlin.de.

ABSTRACT

Background: Recent advances in rapid, low-cost sequencing have opened up the opportunity to study complete genome sequences. The computational approach of multiple genome alignment allows investigation of evolutionarily related genomes in an integrated fashion, providing a basis for downstream analyses such as rearrangement studies and phylogenetic inference.Graphs have proven to be a powerful tool for coping with the complexity of genome-scale sequence alignments. The potential of graphs to intuitively represent all aspects of genome alignments led to the development of graph-based approaches for genome alignment. These approaches construct a graph from a set of local alignments, and derive a genome alignment through identification and removal of graph substructures that indicate errors in the alignment.

Results: We compare the structures of commonly used graphs in terms of their abilities to represent alignment information. We describe how the graphs can be transformed into each other, and identify and classify graph substructures common to one or more graphs. Based on previous approaches, we compile a list of modifications that remove these substructures.

Conclusion: We show that crucial pieces of alignment information, associated with inversions and duplications, are not visible in the structure of all graphs. If we neglect vertex or edge labels, the graphs differ in their information content. Still, many ideas are shared among all graph-based approaches. Based on these findings, we outline a conceptual framework for graph-based genome alignment that can assist in the development of future genome alignment tools.

Show MeSH

Related in: MedlinePlus

The labeling of A-Bruijn graph vertices with one orientation bit per segment does not resolve ambiguity. In this example, both blocks occur three times, twice in the forward orientation and once in the reverse complemented orientation. Combining the orientations of the segments in the two blocks is ambiguous as the two alternative Enredo graph structures prove. In the left Enredo graph structure, the segment in the reverse complemented orientation of one block is combined with a segment in the forward orientation of the other block. In the right Enredo graph structure, the two segments in the reverse complemented orientation occur consecutively.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4020321&req=5

Figure 7: The labeling of A-Bruijn graph vertices with one orientation bit per segment does not resolve ambiguity. In this example, both blocks occur three times, twice in the forward orientation and once in the reverse complemented orientation. Combining the orientations of the segments in the two blocks is ambiguous as the two alternative Enredo graph structures prove. In the left Enredo graph structure, the segment in the reverse complemented orientation of one block is combined with a segment in the forward orientation of the other block. In the right Enredo graph structure, the two segments in the reverse complemented orientation occur consecutively.

Mentions: The first bit in the label ℓinv(e) indicates the orientation of the segment in the source vertex of e, and the second bit the orientation of the segment in the target vertex. It is not sufficient to solely label vertices of G with one orientation bit per segment of the represented block. Figure 7 provides an example where this leads to ambiguity.


Genome alignment with graph data structures: a comparison.

Kehr B, Trappe K, Holtgrewe M, Reinert K - BMC Bioinformatics (2014)

The labeling of A-Bruijn graph vertices with one orientation bit per segment does not resolve ambiguity. In this example, both blocks occur three times, twice in the forward orientation and once in the reverse complemented orientation. Combining the orientations of the segments in the two blocks is ambiguous as the two alternative Enredo graph structures prove. In the left Enredo graph structure, the segment in the reverse complemented orientation of one block is combined with a segment in the forward orientation of the other block. In the right Enredo graph structure, the two segments in the reverse complemented orientation occur consecutively.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4020321&req=5

Figure 7: The labeling of A-Bruijn graph vertices with one orientation bit per segment does not resolve ambiguity. In this example, both blocks occur three times, twice in the forward orientation and once in the reverse complemented orientation. Combining the orientations of the segments in the two blocks is ambiguous as the two alternative Enredo graph structures prove. In the left Enredo graph structure, the segment in the reverse complemented orientation of one block is combined with a segment in the forward orientation of the other block. In the right Enredo graph structure, the two segments in the reverse complemented orientation occur consecutively.
Mentions: The first bit in the label ℓinv(e) indicates the orientation of the segment in the source vertex of e, and the second bit the orientation of the segment in the target vertex. It is not sufficient to solely label vertices of G with one orientation bit per segment of the represented block. Figure 7 provides an example where this leads to ambiguity.

Bottom Line: We show that crucial pieces of alignment information, associated with inversions and duplications, are not visible in the structure of all graphs.Still, many ideas are shared among all graph-based approaches.Based on these findings, we outline a conceptual framework for graph-based genome alignment that can assist in the development of future genome alignment tools.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science, Freie Universität Berlin, Takustr, 9, 14195 Berlin, Germany. birte.kehr@fu-berlin.de.

ABSTRACT

Background: Recent advances in rapid, low-cost sequencing have opened up the opportunity to study complete genome sequences. The computational approach of multiple genome alignment allows investigation of evolutionarily related genomes in an integrated fashion, providing a basis for downstream analyses such as rearrangement studies and phylogenetic inference.Graphs have proven to be a powerful tool for coping with the complexity of genome-scale sequence alignments. The potential of graphs to intuitively represent all aspects of genome alignments led to the development of graph-based approaches for genome alignment. These approaches construct a graph from a set of local alignments, and derive a genome alignment through identification and removal of graph substructures that indicate errors in the alignment.

Results: We compare the structures of commonly used graphs in terms of their abilities to represent alignment information. We describe how the graphs can be transformed into each other, and identify and classify graph substructures common to one or more graphs. Based on previous approaches, we compile a list of modifications that remove these substructures.

Conclusion: We show that crucial pieces of alignment information, associated with inversions and duplications, are not visible in the structure of all graphs. If we neglect vertex or edge labels, the graphs differ in their information content. Still, many ideas are shared among all graph-based approaches. Based on these findings, we outline a conceptual framework for graph-based genome alignment that can assist in the development of future genome alignment tools.

Show MeSH
Related in: MedlinePlus