On Graph-Based Data Structures to Multiple Genome Alignment

Multiple genome alignment (MGA) has become widely used in many different areas in bioinformatics from finding sequences family, detecting structural homologies of genomes, and predicting functions of genomes to predict patient's diseases by comparing DNAs of patients in disease discovery. 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. This review summarizes the presented graphical representation of multiple alignment in large scales and their abilities to represent alignment information and also the role of graph data structures to assist in the development of future genome alignment tools.