Large Grain Alignment (LGA)

Large Grain Alignment (LGA) is a software package that iterates through phases of multiple sequence alignment, phylogeny searches and calculating substitution matrices to provide a large grain optimization alignment that provides more refined alignments then packages like ClustalW and overcomes limitations in current optimization alignment packages such as POY.

Introduction

Perry Ridge started initial development of LGA in 2004 while a member of the Computational Science Lab at Brigham Young University. Currently the package is maintained by Hyrum Carroll, a doctoral student in the same lab. LGA is licensed under the GNU General Public License.

Results

LGA generally performs better then ClustalW by offering a large grain optimization alignment approach that takes considerably less execution time than POY. Figures 1-5 illustrate typical performance found during benchmarking with the data sets listed below.

Figure 1. Parsimony scores for LGA, ClustalW and MUSCLE for data sets 100HIV, bugs1, 18ML, actino1, actino2, actino3 and 28ML. The numbers above the bars show the difference in the parsimony scores between LGA and the respective algorithm. Positive values indicate that LGA achieved a more parsimonious alignment.

Figure 2. Parsimony scores for LGA, ClustalW and MUSCLE for data sets euk2, 50taxa, euk1, euk3, kpap1, 200bug and MP. The numbers above the bars show the difference in the parsimony scores between LGA and the respective algorithm. Positive values indicate that LGA achieved a more parsimonious alignment.

Download LGA

The latest version of LGA can be downloaded as a tar ball (.tar.gz) or a zipped file (.zip). After uncompressing the respective file, see the file README for a working example.

Data sets

The data sets used in the performance analysis of LGA are listed below (click on the data set name for the FASTA file):

Name	Description
bugs1	Two nuclear ribosomal genes for a wide diversity of hexapod species, provided by Michael Whiting, Brigham Young University
18ML	From the Genome website
actino1	Random subset of the actino bacteria dataset provided by Usman Roshan
actino2	Random subset of the actino bacteria dataset provided by Usman Roshan
actino3	Random subset of the actino bacteria dataset provided by Usman Roshan
28ML	From the Genome website
euk2	Random subset of the eukaryote dataset provided by Usman Roshan
50taxa	Two nuclear ribosomal genes for a wide diversity of hexapod species, provided by Michael Whiting, Brigham Young University
euk1	Random subset of the eukaryote dataset provided by Usman Roshan
euk3	Random subset of the eukaryote dataset provided by Usman Roshan
kpap1	Obtained from the following website: http://hades.biochem.dal.ca/Rogerlab/Datasets/datasets.html. kap1 is small subunit ribosomal RNA alignment.
200bug	From the Genome website
MP	18S ribosomal DNA from insects

Technical Report

Click here for the technical report version.