Stadick, S. | bioRxiv Science

bioRxiv2025

Ish: SIMD and GPU Accelerated Local and Semi-Global Alignment as a CLI Filtering Tool

BackgroundFiltering records using command line tools is a staple of Bioin-formatics. In analysis pipelines and in day-to-day research tools such as awk, grep, and cut are the workhorses of much of our data crunching. To date, there is no command line utility for performing index-free alignment-based filtering of records. ResultsIsh is a classic and composable unix-style CLI tool. It takes a query and filters the input target records to only those that match the input query with a threshold alignment score, using a selectable alignment algorithm. The core alignment algorithms for Ish meet or exceed the performance of their reference implementations for both SIMD and GPU alignment, as measured by gigacell updates per second (GCUPs). ConclusionsIsh fills a longstanding gap in Bioinformatics tooling by offering a CLI utility for index-free alignment-based record filtering. Additionally, it provides meaningfully improved versions of the classic striped local and semi-global full dynamic programming algorithms, along with a GPU-based semi-global alignment method.

bioinformatics↗

bioRxiv2022

Fast and Accurate Kinship Estimation Using Sparse SNPs in Relatively Large Database Searches

1.Forensic genetic genealogy (FGG) has primarily relied upon dense single nucleotide polymorphism (SNP) profiles from forensic samples or unidentified human remains queried against online genealogy database(s) of known profiles generated with SNP microarrays or from whole genome sequencing (WGS). In these queries, SNPs are compared to database samples by locating contiguous stretches of shared SNP alleles that allow for detection of genomic segments that are identical by descent (IBD) among biological relatives (kinship). This segment-based approach, while robust for detecting distant relationships, generally requires DNA quantity and/or quality that are sometimes not available in forensic casework samples. By focusing on SNPs with maximal discriminatory power and using an algorithm designed for a sparser SNP set than those from microarray typing, performance similar to segment matching was reached even in difficult casework samples. This algorithm locates shared segments using kinship coefficients in "windows" across the genome. The windowed kinship algorithm is a modification of the PC-AiR and PC-Relate tools for genetic relatedness inference, referred to here as the "whole genome kinship" approach, that control for the presence of unknown or unspecified population substructure. Simulated and empirical data in this study, using DNA profiles comprised of 10,230 SNPs (10K multiplex) targeted by the ForenSeq Kintelligence Kit demonstrate that the windowed kinship approach performs comparably to segment matching for identifying first, second and third degree relationships, reasonably well for fourth degree relationships, and with fewer false kinship associations. Selection criteria for the 10K SNP PCR-based multiplex and functionality of the windowed kinship algorithm are described.

genomics↗