Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 6 of 6
Full-Text Articles in Physical Sciences and Mathematics
Hardware Accelerated Sequence Alignment With Traceback, Scott Lloyd, Quinn O. Snell
Hardware Accelerated Sequence Alignment With Traceback, Scott Lloyd, Quinn O. Snell
Faculty Publications
Biological sequence alignment is an essential tool used in molecular biology and biomedical applications. The growing volume of genetic data and the complexity of sequence alignment present a challenge in obtaining alignment results in a timely manner. Known methods to accelerate alignment on reconfigurable hardware only address sequence comparison, limit the sequence length, or exhibit memory and I/O bottlenecks. A space-efficient, global sequence alignment algorithm and architecture is presented that accelerates the forward scan and traceback in hardware without memory and I/O limitations. With 256 processing elements in FPGA technology, a performance gain over 300 times that of a desktop …
Sequence Alignment With Traceback On Reconfigurable Hardware, Scott Lloyd, Quinn O. Snell
Sequence Alignment With Traceback On Reconfigurable Hardware, Scott Lloyd, Quinn O. Snell
Faculty Publications
Biological sequence alignment is an essential tool used in molecular biology and biomedical applications. The growing volume of genetic data and the complexity of sequence alignment present a challenge in obtaining alignment results in a timely manner. Known methods to accelerate alignment on reconfigurable hardware only address sequence comparison, limit the sequence length, or exhibit memory and I/O bottlenecks. A space-efficient, global sequence alignment algorithm and architecture is presented that accelerates the forward scan and traceback in hardware without memory and I/O limitations. With 256 processing elements in FPGA technology, a performance gain over 300 times that of a desktop …
Large Grain Size Stochastic Optimization Alignment, Hyrum Carroll, Mark J. Clement, Perry Ridge, Dan Sneddon, Quinn O. Snell
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 …
Phylogenetic Analysis Of Large Sequence Data Sets, Hyrum Carroll, Mark J. Clement, Keith Crandall, Quinn O. Snell
Phylogenetic Analysis Of Large Sequence Data Sets, Hyrum Carroll, Mark J. Clement, Keith Crandall, Quinn O. Snell
Faculty Publications
Phylogenetic analysis is an integral part of biological research. As the number of sequenced genomes increases, available data sets are growing in number and size. Several algorithms have been proposed to handle these larger data sets. A family of algorithms known as disc covering methods (DCMs), have been selected by the NSF funded CIPRes project to boost the performance of existing phylogenetic algorithms. Recursive Iterative Disc Covering Method 3 (Rec-I-DCM3), recursively decomposes the guide tree into subtrees, executing a phylogenetic search on the subtree and merging the subtrees, for a set number of iterations. This paper presents a detailed analysis …
Jumpstarting Phylogenetic Analysis, Mark J. Clement, Keith A. Crandall, Kevin Seppi, Quinn O. Snell
Jumpstarting Phylogenetic Analysis, Mark J. Clement, Keith A. Crandall, Kevin Seppi, Quinn O. Snell
Faculty Publications
When a new epidemic strikes, it is often important to determine the relationship between the current organism and others that have been successfully treated previously. The phylogenetic analysis problem generates the most likely family tree for a group of organisms based on DNA sequence data. This process can take a prohibitively long period of time with current algorithms. If trees resulting from prior searches are used to seed the search, correct trees can be found much more quickly. This jumpstarting algorithm can generate superior phylogenetic solutions much more quickly than existing algorithms.
Parallel Phylogenetic Inference, Mark J. Clement, David Mclaughlin, Quinn O. Snell, Michael Whiting
Parallel Phylogenetic Inference, Mark J. Clement, David Mclaughlin, Quinn O. Snell, Michael Whiting
Faculty Publications
Recent advances in DNA sequencing technology have created large data sets upon which phylogenetic inference can be performed. However, current research is limited by the prohibitive time necessary to perform tree search on even a reasonably sized data set. Some parallel algorithms have been developed but the biological research community does not use them because they don’t trust the results from newly developed parallel software. This paper presents a new phylogenetic algorithm that allows existing, trusted phylogenetic software packages to be executed in parallel using the DOGMA parallel processing system. The results presented here indicate that data sets that currently …