OVT-MLCS: An Online Visual Tool for MLCS Mining from Long or Big Sequences

This paper introduces OVT-MLCS, an online visual tool that overcomes existing limitations in mining multiple longest common subsequences (MLCS) from long or big sequences by employing a novel KP-MLCS algorithm and offering real-time interactive visualization for effective analysis and pattern discovery.

The Gist

Imagine you are a detective trying to solve a massive mystery. You have three (or more) very long, messy storybooks written in a secret code. Your job is to find the longest sentences that appear in all of these books exactly the same way. In the world of computer science, this is called finding the Multiple Longest Common Subsequence (MLCS).

Usually, this is a nightmare. If the books are short, it's easy. But if the books are "Big Sequences" (like the 30,000-letter genetic codes of viruses or cancer patients), traditional detective tools crash. They run out of memory (like a brain trying to hold too many thoughts at once) or take years to solve.

This paper introduces a new, super-smart detective tool called OVT-MLCS. Here is how it works, explained simply:

1. The Problem: The "Library of Babel"

Imagine trying to find a specific sentence hidden in a library with millions of books, where every book is slightly different.

• Old Tools: They try to read every single page of every book, comparing them one by one. For huge DNA sequences, this creates a "memory explosion." It's like trying to carry the entire library in your backpack; you drop it, and the data is lost.
• The Result: Scientists couldn't analyze long DNA sequences effectively, hindering research into things like cancer or virus evolution.

2. The Solution: The "Key Point" Shortcut

The authors created a new algorithm called KP-MLCS.

• The Analogy: Instead of reading every single word in the storybooks, the new algorithm acts like a highlighter. It ignores the boring, repetitive parts and only marks the "Key Points" where the stories actually match up.
• The Result: It builds a tiny, efficient map (called a graph) of just the important connections. This map is so small and organized that it fits easily in memory, even for massive DNA sequences.

3. The Tool: OVT-MLCS (The Visual Dashboard)

The paper isn't just about the math; it's about a web-based tool that lets anyone use this power. Think of OVT-MLCS as a Google Maps for DNA.

• Real-Time Visualization: Instead of giving you a wall of text, it draws a colorful, interactive map. You can zoom in and out, drag the map around, and see the "common patterns" (the shared sentences) light up.
• The "Top-K" Feature: Sometimes, there are thousands of matching sentences. You don't need to see them all. The tool can show you just the Top 10 best matches, filtering out the noise so you can focus on what matters.
• Two-Way Interaction: This is the coolest part. You can look at the map, click on a specific pattern, and the tool instantly shows you exactly where that pattern appears in the original DNA sequences. It's like clicking a pin on a map and instantly seeing the street view.

4. Why This Matters: Real-Life Superpowers

The paper demonstrates this tool with two real-world scenarios:

• Scenario A: The Virus Hunter

  • Goal: Compare 30,000-letter DNA sequences of the COVID-19 virus from different countries to see how they evolved.
  • Old Way: Impossible or took days.
  • OVT-MLCS Way: Done in 1.5 hours. The tool instantly highlights the differences, helping scientists design better vaccines.

• Scenario B: The Cancer Detective

  • Goal: Look at liver cancer patient DNA to find common mutation spots (the "bad guys" causing cancer).
  • Old Way: Too much data to handle.
  • OVT-MLCS Way: Done in 25 minutes. The tool spots the common patterns across patients, helping doctors create personalized treatments.

Summary

OVT-MLCS is like giving a detective a high-tech, interactive map instead of a pile of paper files. It takes the impossible task of finding patterns in massive DNA sequences, shrinks the problem down to its "key points," and lets scientists see the answers instantly through a beautiful, easy-to-use visual interface. It turns a computational nightmare into a simple, click-and-discover experience.

Technical Summary

1. Problem Statement

The paper addresses the challenge of mining Multiple Longest Common Subsequences (MLCS) from a set of three or more sequences over a finite alphabet. This is a classical NP-hard problem with critical applications in bioinformatics (e.g., DNA/protein analysis, cancer gene detection, virus evolution research).

Key Challenges Identified:

• Scalability: Existing exact MLCS algorithms and tools (e.g., BLAST, Clustal Omega, DOP-based algorithms) fail to handle long (length $\ge$ 1,000) or big (length $\ge$ 10,000) sequences.
• Memory Explosion: Traditional approaches rely on problem-solving graph models (MLCS-DAG) that generate an overwhelming number of nodes and edges, causing memory overflow.
• Time Complexity: The computational cost is prohibitively high for big data.
• Lack of Visualization: Existing tools output results sequentially without intuitive structural or visual patterns, making it difficult to identify common patterns among thousands of mined MLCS solutions.
• Gap: There is currently no exact tool capable of mining, visualizing, and analyzing MLCSs from big sequences while meeting user needs for interactivity and pattern discovery.

2. Methodology

The authors propose a comprehensive solution consisting of a novel algorithm, a compact representation method, and a full-stack web application.

A. The KP-MLCS Algorithm

The core algorithmic contribution is KP-MLCS (Key Point-based MLCS).

• Graph Model ($DAG_{KP}$): Unlike traditional Dominant Point (DOP) algorithms that generate many useless nodes, KP-MLCS constructs a specialized graph model containing only key points (nodes and edges) that contribute to the final MLCS mining. This drastically reduces the graph size.
• Parallel Processing: The system utilizes multi-threaded concurrent mining to accelerate computation.
• Memory Management (Serialization/De-serialization):
  • To prevent memory explosion, the system employs a Supporting Layer that dynamically monitors memory usage.
  • When memory reaches a threshold, the system automatically serializes (saves to disk) the first several layers of the $DAG_{KP}$ subgraph to an H2 database.
  • When data is needed for computation or display, it is de-serialized (loaded back into memory) layer by layer.

B. Top-K Mining Strategy

• Recognizing that big sequences can yield tens of thousands of MLCS solutions, the tool supports Top-K mining.
• It uses a score function based on the $DAG_{KP}$ to identify and display only the top-$k$ optimal MLCSs (those with the fewest discontinuous spaces), filtering out massive redundant results.

C. OVT-MLCS System Architecture

The system is a lightweight, browser-based Web application built with Java (AntX6, Beangle Web), Bootstrap, WebSocket, and H2 Database.

• GUI: Provides an interactive interface for inputting sequences, mining, and visualizing results.
• Visualization Engine: Uses Antv-X6 and SVG to render the $DAG_{KP}$ graph. Each path in the graph represents an MLCS solution.
• Interactive Insight:
  • Common Pattern Detection: Automatically highlights subgraph sections with width 1 in the $DAG_{KP}$, revealing common patterns without additional calculation.
  • Statistical Analysis: Displays pie charts (character proportions) and line charts (sequence similarities).
  • Two-way Interaction: Users can inspect input sequences and mined results simultaneously, with real-time statistical updates.

3. Key Contributions

1. First Exact Tool for Big Sequences: OVT-MLCS is the first exact MLCS mining tool capable of handling sequences with lengths up to 5,000 (and potentially larger via the "big sequence" definition of $\ge$ 10,000 in the abstract context), overcoming the memory/time barriers of previous tools.
2. Novel Algorithm (KP-MLCS): Introduces a key-point-based graph model that eliminates non-critical nodes, significantly reducing space and time complexity ($O(dN) + O(E)$).
3. Integrated Visualization & Interaction: Provides a unified platform for mining, storing, and visualizing MLCSs. It uniquely allows users to interactively explore common patterns and statistical data in real-time.
4. Practical Utility: Supports both "Exact" (all MLCSs) and "Top-K" mining modes, with features for downloading results in text (.text) and graph (.xml) formats.

4. Results and Demonstration

The paper validates the system through two biomedical use cases:

• Use Case 1: COVID-19 Virus Evolution
  • Data: ~30,000 bp genome sequences of COVID-19 and flu-causing coronaviruses.
  • Goal: Determine evolutionary relationships and similarities.
  • Outcome: The user successfully mined and analyzed the data using Exact/Top-K Mining and Insight features in 1.5 hours.
• Use Case 2: Liver Cancer Gene Analysis
  • Data: 11 complete genome sequences (length $\ge$ 10,000) from liver cancer patients.
  • Goal: Discover mutation target locations and analyze commonality/individuality.
  • Outcome: Using Top-K Mining and two-way interaction, the user obtained expected results in 25 minutes.

Performance: For 3 long/big sequences, mining is completed in seconds (long) to minutes (big), a significant improvement over existing methods which often fail or take impractical amounts of time.

5. Significance

• Bridging the Gap: OVT-MLCS fills a critical void in bioinformatics and data mining by enabling the exact analysis of massive sequence data that was previously intractable.
• Enhanced Pattern Discovery: By compressing thousands of MLCS solutions into a single, interactive graph ($DAG_{KP}$), it allows researchers to intuitively spot common patterns and evolutionary links that are invisible in raw text outputs.
• Accessibility: As an open-source, online visual tool, it lowers the barrier for researchers to perform complex MLCS mining without needing deep expertise in algorithmic implementation.
• Future Impact: The authors believe this tool will promote wider applications of MLCS in cancer diagnosis, vaccine development, and large-scale genomic studies.

Availability: The source code and artifacts are available at https://github.com/OVT-MLCS/OVT-MLCS-Tool.