2025/11/12 by Md. Tanzeem Rahat, Md. Manzurul Hasan, Rahat, Md. Tanzeem +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2511.08958
openalex publication_date 2025/11/12 · openalex created_date 2025/11/14 · openalex updated_date 2026/07/31
Given two sequences A[1..n] and B[1..m] over a totally ordered alphabet, the Longest Common Bitonic Subsequence (LCBS) problem asks for a longest common subsequence that is strictly increasing up to a single peak element and strictly decreasing thereafter (allowing either phase to be empty). The only explicitly documented approach evaluates a quadratic dynamic program over the full n× m grid, which is prohibitive on large inputs. We present two exact algorithms. First, we give a simple Θ(nm)-time baseline that computes LCBS by combining a longest common increasing subsequence (LCIS) computation on (A,B) with a second LCIS computation on the reversed inputs, and then maximizing INC(i,j)+DEC(i,j)-1 over all common peaks. The method is constructive via parent pointers. Second, we develop an instance-sensitive algorithm whose running time depends on the number M of matching pairs (i,j) with A[i]=B[j]. We view matches as vertices of a dominance-ordered poset and compute the increasing and decreasing halves by two 2D dominance DP passes supported by orthogonal range-maximum data structures, followed by a linear peak scan. With a standard 2D range tree (or equivalent), this yields O(Mlog2M + M + (n+m)log(n+m)) time and O(Mlog M) space, and it improves over the dense baseline whenever Mlog2 M≪ nm.