Physical Sciences and Mathematics Commons^™

Large Grain Size Stochastic Optimization Alignment, Hyrum Carroll, Mark J. Clement, Perry Ridge, Dan Sneddon, Quinn O. Snell

Faculty Publications

DNA sequence alignment is a critical step in identifying homology between organisms. The most widely used alignment program, ClustalW, is known to suffer from the local minima problem, where suboptimal guide trees produce incorrect gap insertions. The optimization alignment approach, has been shown to be effective in combining alignment and phylogenetic search in order to avoid the problems associated with poor guide trees. The optimization alignment algorithm operates at a small grain size, aligning each tree found, wasting time producing multiple sequence alignments for suboptimal trees. This research develops and analyzes a large grain size algorithm for optimization alignment that …