Browsing by Subject "alignment"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Efficiency of Shared-Memory Multiprocessors for a Genetic Sequence Similarity Search Algorithm
    (1997) Chi, Ed Huai-hsin; Shoop, Elizabeth; Carlis, John; Retzel, Ernest; Riedl, John
    Molecular biologists who conduct large-scale genetic sequencing projects are producing an ever-increasing amount of sequence data. GenBank, the primary repository for DNA sequence data, is doubling in size every 1.3 years. Keeping pace with the analysis of these data is a difficult task. One of the most successful technique, for analyzing genetic data is sequence similarity analysis-the comparison of unknown sequences against known sequences kept in databases. As biologists gather more sequence data, sequence similarity algorithms are more and more useful, but take longer and longer to run. BLAST is one of the most popular sequence similarity algorithms in me today, but its running time is approximately proportional to the size of the database. Sequence similarity analysis using BLAST is becoming a bottleneck in genetic sequence analysis. This paper analyzes the performance of BLAST on SMPs, to improve our theoretical and practical understanding of the scalability of the algorithm. Since the database sizes are growing faster than the improvements in processor speed we expect from Moore's law, multiprocessor architectures appear to be the only way to meet the need for performance.
  • Thumbnail Image
    Item
    High-performance tools for precise microbiome characterization
    (2018-08) Al-Ghalith, Gabriel
    The microbiome, defined as the vast number of microorganisms inhabiting both human and non-human environments, has been associated with human disease as well as other important ecological phenomena. However, its quantitative study is complicated in part by measurement error and computational limitations, pointing to a need for more sensitive and reproducible DNA sequence analysis techniques. To this end, I have developed a variety of improved methods including a flexible short-read quality control pipeline, curated databases of marker genes and whole genomes, streamlined OTU picking software, and a high-throughput optimal aligner with taxonomy interpolation. Together, these methods represent advancements over traditional sequence analysis pipelines and may improve the quality of downstream statistical analyses.