Indexing Graphs for Path Queries with Applications in Genome Research

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Traditional genome analysis relies on linear sequence representations.
• Existing methods struggle with genomic variations and complex structures like splicing.

Purpose of the Study:

• To introduce a generic graph-based representation for genomic data.
• To extend the Burrows-Wheeler Transform (BWT) for graph structures.
• To apply these extensions to critical bioinformatics tasks.

Main Methods:

• Developed an extended Burrows-Wheeler Transform (BWT) for acyclic directed labeled graphs.
• Applied the extended BWT to create a pan-genome index for read alignment.
• Tailored the technique for split-read alignment using splicing graphs.

Main Results:

• Demonstrated the feasibility and applicability of graph-based genome representation.
• Achieved significant improvements in alignment accuracy for highly-polymorphic genome regions using the pan-genome index.
• Successfully applied the method to read and split-read alignment challenges.

Conclusions:

• Graph representations offer a powerful alternative to canonical sequences for genomic data.
• The extended BWT approach enhances alignment accuracy and analytical capabilities.
• This method holds promise for various applications including probe design and assembly analysis.