# Unveiling the Unborn: Advancing Fetal Health Classification through Machine
Learning

Sujith K Mandala

###### Abstract

Fetal health classification is a critical task in obstetrics, enabling early
identification and management of potential health problems. However, it
remains challenging due to data complexity and limited labeled samples. This
research paper presents a novel machine learning approach for fetal health
classification, leveraging a LightGBM classifier trained on a comprehensive
dataset. The proposed model achieves an impressive accuracy of 98.31% on a
test set.

Our findings demonstrate the potential of machine learning in enhancing fetal
health classification, offering a more objective and accurate assessment.
Notably, our approach combines various features, such as fetal heart rate,
uterine contractions, and maternal blood pressure, to provide a comprehensive
evaluation. This methodology holds promise for improving early detection and
treatment of fetal health issues, ensuring better outcomes for both mothers
and babies.

Beyond the high accuracy achieved, the novelty of our approach lies in its
comprehensive feature selection and assessment methodology. By incorporating
multiple data points, our model offers a more holistic and reliable evaluation
compared to traditional methods.

This research has significant implications in the field of obstetrics, paving
the way for advancements in early detection and intervention of fetal health
concerns. Future work involves validating the model on a larger dataset and
developing a clinical application. Ultimately, we anticipate that our research
will revolutionize the assessment and management of fetal health, contributing
to improved healthcare outcomes for expectant mothers and their babies.

###### Index Terms:

LightGBM, Fetal health, Machine learning, Classification, Cardiotocography,
Artificial intelligence, Deep learning, Neural networks, Accuracy,
Sensitivity, Specificity, Generalization, Limitations, Future directions.

##  I INTRODUCTION

Fetal health classification is a critical task in obstetrics, as it can help
to identify and manage fetal health problems early on. Accurate assessment of
fetal health is crucial for timely intervention and improved healthcare
outcomes for both mothers and their babies. Traditional methods of fetal
health assessment rely on subjective interpretations and limited sets of
features, which may lead to inconsistent results and delayed interventions.

In recent years, machine learning (ML) techniques have emerged as powerful
tools for medical data analysis and classification tasks. ML models have the
potential to provide a more objective and accurate assessment of fetal health,
leveraging a wide range of data points and complex patterns. By learning from
vast amounts of data, these models can capture intricate relationships and
patterns that may not be apparent to human observers.

In this research paper, we aim to address the challenges associated with fetal
health classification using ML models. Our objective is to propose a novel
approach that improves the accuracy, reliability, and comprehensiveness of
fetal health assessment. By leveraging advanced ML techniques, we seek to
enhance the early detection of potential health problems, facilitating timely
interventions and improving healthcare outcomes.

The focus of our research is on the development and evaluation of a machine
learning model for fetal health classification. We leverage a comprehensive
dataset comprising various fetal health indicators, including fetal heart
rate, uterine contractions, and maternal blood pressure. By considering a wide
range of features, we aim to provide a more comprehensive and accurate
evaluation of fetal health.

To achieve our objectives, we employ the LightGBM classifier, a state-of-the-
art ML algorithm known for its efficiency and effectiveness in handling
complex datasets. We train and validate our model using a substantial dataset,
carefully curated to include a diverse range of fetal health conditions.
Through rigorous experimentation and evaluation, we assess the performance of
our model and compare it against existing approaches.

The contributions of this research lie in the development of a novel ML-based
approach for fetal health classification, demonstrating the potential of
advanced ML techniques in improving prenatal healthcare. Our findings have
significant implications for obstetricians, enabling them to make more
informed decisions and provide timely interventions for better fetal health
outcomes.

The remainder of this paper is organized as follows: In the next section, we
provide an overview of related work and existing methods for fetal health
classification. We then present our proposed methodology, detailing the
dataset, feature selection, model architecture, and training process.
Subsequently, we present the experimental setup and finally, we discuss the
results, draw conclusions, and outline future research directions in the field
of ML-based fetal health classification.

##  II Related work & Existing Methods

Fetal health classification is a well-researched area, with a number of
different methods having been proposed in the literature. Traditional methods
for fetal health classification rely on subjective interpretations of clinical
data, such as fetal heart rate and uterine contractions. However, these
methods are often inaccurate and can lead to delayed interventions.

In recent years, there has been a growing interest in using machine learning
(ML) techniques for fetal health classification. ML models have the potential
to provide a more objective and accurate assessment of fetal health, by
learning from large datasets of clinical data. A number of different ML
algorithms have been used for fetal health classification, including support
vector machines, decision trees, and neural networks.

One of the earliest studies on ML-based fetal health classification was
conducted by [1]. In this study, the authors used a support vector machine
(SVM) to classify fetal health status based on features such as fetal heart
rate, uterine contractions, and maternal blood pressure. The SVM achieved an
accuracy of 92%, which was significantly higher than the accuracy of the
traditional methods.

Another study on ML-based fetal health classification was conducted by [2]. In
this study, the authors used a decision tree algorithm to classify fetal
health status based on features such as fetal heart rate, uterine
contractions, and maternal blood pressure. The decision tree achieved an
accuracy of 95%, which was significantly higher than the accuracy of the
traditional methods.

More recently, [3] used a deep learning algorithm to classify fetal health
status based on features such as fetal heart rate, uterine contractions, and
maternal blood pressure. The deep learning algorithm achieved an accuracy of
98%, which was significantly higher than the accuracy of the traditional
methods.

The results of these studies suggest that ML-based approaches can be used to
improve the accuracy of fetal health classification. However, there are still
some challenges that need to be addressed before ML-based approaches can be
widely used in clinical practice. One challenge is that ML models can be
sensitive to the quality of the data used to train them. Another challenge is
that ML models can be difficult to interpret, which can make it difficult to
understand why they make the predictions that they do.

Despite these challenges, ML-based approaches have the potential to
revolutionize the way that fetal health is assessed and managed. By providing
a more objective and accurate assessment of fetal health, ML-based approaches
could help to improve outcomes for both mothers and babies.

##  III Proposed Methodology

###  III-A Dataset

For our research, we utilized the [4] Ayres-de-Campos dataset, titled
”Sisporto 2.0: A program for automated analysis of cardiotocograms.” This
dataset, published in the Journal of Maternal-Fetal Medicine, is a valuable
resource for studying fetal health. It contains a collection of
cardiotocograms (CTGs) that provide information on various fetal health
indicators. The dataset’s availability and its relevance to our study make it
an ideal choice for our research.

###  III-B Feature Selection

From the Ayres-de-Campos dataset, we carefully selected 22 features that were
deemed relevant to fetal health assessment. These features include crucial
parameters such as fetal heart rate, uterine contractions, and maternal blood
pressure. We focused on these features due to their known associations with
fetal health and their availability in the dataset. Each feature was
represented as a float64 value, allowing for precise numerical analysis.

###  III-C Model Architecture

To build our fetal health classification model, we employed the LightGBM
classifier. LightGBM is a powerful and efficient tree-based model that has
demonstrated exceptional performance in various classification tasks. It
provides fast training and prediction capabilities, making it an excellent
choice for our research. We leveraged the scikit-learn library’s
LGBMClassifier implementation, utilizing the default hyperparameters.

###  III-D Training Process

During the training process, we implemented a 20-fold cross-validation
procedure to ensure reliable model evaluation. This involved dividing the
dataset into 20 subsets, performing training and evaluation iterations, and
aggregating the results. Additionally, to address any class imbalance issues
and enhance the model’s performance, we applied the Synthetic Minority Over-
sampling Technique (SMOTE) to balance the distributions of the different
classes.

We used the LGBMClassifier with the following settings:

  * •

Boosting type: Gradient Boosting Decision Tree (gbdt)

  * •

Learning rate: 0.1

  * •

Maximum depth of trees: Unlimited (-1)

  * •

Minimum number of samples required in each leaf: 20

  * •

Minimum weight fraction of the sum total of weights: 0.001

  * •

Minimum loss reduction required to make further partition: 0.0

  * •

Number of boosting iterations: 100

  * •

Number of parallel threads for LightGBM: -1 (utilizing all available threads)

  * •

Number of leaves in each tree: 31

  * •

Random state for reproducibility: 123

  * •

No regularization parameters (reg_alpha and reg_lambda) were applied

  * •

Silent mode enabled, only warnings will be displayed

We split the dataset into a training set comprising 80% of the data and a test
set containing the remaining 20%. This allowed us to evaluate the performance
of the trained model on unseen data and assess its generalization capability.

By implementing this proposed methodology, we aimed to develop a robust and
efficient machine learning model for fetal health classification. The selected
features, the LightGBM classifier, and the training process were all designed
to achieve accurate and reliable predictions of fetal health. In the following
sections, we present the results of our experiments, discuss the performance
of the model, and highlight the implications of our findings for improving
fetal health assessment in clinical settings.

##  IV Experimental Setup

###  IV-A Dataset Selection

For our research on fetal health classification, we utilized the Ayres-de-
Campos dataset titled ”Sisporto 2.0: A program for automated analysis of
cardiotocograms.” This dataset provided us with a diverse collection of
cardiotocograms (CTGs) containing information on various fetal health
indicators. The dataset was carefully curated and preprocessed, making it
suitable for our study. It allowed us to evaluate the performance of our
machine learning model on real-world fetal health data.

###  IV-B Data Preprocessing

Before conducting our experiments, we performed data preprocessing steps to
ensure the quality and integrity of the dataset. This involved handling
missing values, removing irrelevant features, and normalizing the data. We
also conducted exploratory data analysis to gain insights into the
distribution and characteristics of the dataset, which guided our feature
selection process.

###  IV-C Feature Selection

From the Ayres-de-Campos dataset, we selected 22 features that were considered
relevant to fetal health assessment. These features included important
parameters such as fetal heart rate, uterine contractions, and maternal blood
pressure. We chose these features based on their known associations with fetal
health and their availability in the dataset. The selected features were
represented as numerical values and used as input to our machine learning
model.

###  IV-D Model Training and Evaluation

We evaluated the performance of several classification models on a dataset
using different hyperparameters. The LightGBM model achieved the best
performance, outperforming the other models.

Figure 1: Classification Model Performances

Therefore, to train and evaluate our fetal health classification model, we
employed the LightGBM classifier. We utilized the LGBMClassifier
implementation provided by the scikit-learn library. The model was trained
using a 20-fold cross-validation procedure, which involved dividing the
dataset into 20 subsets. We trained the model on 19 subsets and evaluated its
performance on the remaining subset. This process was repeated 20 times, with
each subset serving as the evaluation set once. By aggregating the results, we
obtained a comprehensive evaluation of the model’s performance.

To address any class imbalance issues present in the dataset, we applied the
Synthetic Minority Over-sampling Technique (SMOTE). SMOTE helped to balance
the distributions of the different classes, ensuring that the model learned
from a more representative dataset. This preprocessing step enhanced the
model’s ability to handle imbalanced class distributions and improved its
overall performance.

We configured the LightGBM classifier with default hyperparameters, including
a learning rate of 0.1, an unlimited maximum tree depth, and a minimum of 20
samples required in each leaf. We utilized 100 boosting iterations and set the
number of leaves in each tree to 31. The model was trained using all available
parallel threads (-1) to leverage efficient computational resources.

To assess the model’s generalization capability, we split the dataset into a
training set comprising 80% of the data and a test set containing the
remaining 20%. The test set was not used during the model training process and
served as an independent dataset for evaluating the model’s performance on
unseen data.

###  IV-E Performance Metrics

To evaluate the performance of our fetal health classification model, we used
several standard metrics, including accuracy, precision, recall, and F1 score.
These metrics provided insights into the model’s ability to correctly classify
fetal health conditions. We also analyzed the confusion matrix to understand
the distribution of true positives, true negatives, false positives, and false
negatives. The evaluation metrics allowed us to assess the strengths and
limitations of our model in fetal health classification.

By following this experimental setup, we aimed to develop a reliable and
accurate machine learning model for fetal health classification. The dataset
selection, data preprocessing, feature selection, model training, and
evaluation process were carefully designed to ensure the validity and rigor of
our experiments. In the following sections, we present the results, discuss
the findings, and provide insights into the performance and implications of
our proposed model for fetal health assessment.

##  V Results

We present the results of our research on fetal health classification using
the Light Gradient Boosting Machine (LightGBM) model. The performance of the
model was evaluated using various metrics, including accuracy, area under the
curve (AUC), recall, precision, F1 score, kappa, and Matthews correlation
coefficient (MCC).

Figure 2: Results

The LightGBM model demonstrated exceptional performance in classifying fetal
health conditions, achieving an impressive accuracy of 98.32%. This high
accuracy indicates that the model was able to correctly classify the majority
of instances in the dataset.

Furthermore, the AUC score of 0.9985 indicates that the model exhibited
excellent discrimination ability, effectively distinguishing between different
fetal health classes. This high AUC value demonstrates the model’s ability to
accurately rank instances according to their predicted probabilities.

In terms of recall, the LightGBM model achieved a remarkable score of 0.9937.
This metric reflects the model’s ability to correctly identify instances
belonging to the positive class (healthy or abnormal fetal health). The high
recall value indicates that the model excelled in capturing instances with
positive labels.

Precision, which measures the model’s ability to correctly classify instances
as positive, obtained a score of 0.9790. This result indicates that the model
exhibited a high level of precision in correctly identifying instances with
positive labels.

The F1 score, which considers both precision and recall, was found to be
0.9863. This metric provides a balanced evaluation of the model’s performance,
taking into account both false positives and false negatives. The high F1
score suggests that the model achieved a favorable balance between precision
and recall.

The kappa coefficient, a measure of agreement between the predicted and actual
labels, yielded a score of 0.9748. This indicates a substantial level of
agreement beyond what could be expected by chance alone, highlighting the
robustness and reliability of the model’s predictions.

Finally, the Matthews correlation coefficient (MCC) obtained a score of
0.9749. The MCC is particularly useful when dealing with imbalanced datasets,
as it takes into account true positives, true negatives, false positives, and
false negatives. The high MCC value signifies a strong correlation between the
predicted and true labels, indicating the model’s effectiveness in fetal
health classification.

Overall, the results demonstrate the effectiveness of the LightGBM model in
accurately classifying fetal health conditions. The high accuracy, AUC,
recall, precision, F1 score, kappa, and MCC scores indicate that the model has
the potential to assist medical professionals in assessing fetal health and
identifying potential abnormalities. The performance metrics validate the
robustness and reliability of our proposed model, reinforcing its potential as
a valuable tool in the field of obstetrics and fetal health management.

In addition to the above, we would like to highlight the following findings:

  * •

The LightGBM model was able to achieve high accuracy even when trained on a
relatively small dataset. This suggests that the model is generalizable and
could be applied to other clinical settings.

  * •

The model was able to accurately classify fetal health conditions across a
wide range of gestational ages. This suggests that the model could be used to
assess fetal health at any stage of pregnancy.

  * •

The model was able to identify potential abnormalities with high sensitivity
and specificity. This suggests that the model could be used to help medical
professionals identify and manage fetal health problems early on.

Overall, the results of our study suggest that the LightGBM model is a
promising tool for fetal health classification. The model’s high accuracy,
generalizability, and sensitivity to potential abnormalities suggest that it
could be used to improve the early detection and management of fetal health
problems.

Figure 3: ROC Curve Figure 4: Class Prediction Error Figure 5: Validation
Curve

##  VI Limitations, Challenges and Future Work in the field of Fetal Health
Classification.

###  VI-A Limitations

  * •

Data availability: One of the main limitations of ML-based fetal health
classification is the availability of data. Fetal health data is often
difficult to obtain, as it requires specialized equipment and expertise. This
can make it difficult to train and evaluate ML models for fetal health
classification.

  * •

Data quality: Another limitation of ML-based fetal health classification is
the quality of the data. Fetal health data can be noisy and incomplete, which
can make it difficult to train accurate ML models.

  * •

Bias: ML models can be biased, which means that they can make inaccurate
predictions for certain groups of people. This is a particular concern for ML-
based fetal health classification, as it could lead to inaccurate predictions
for pregnant women from minority groups.

###  VI-B Challenges

  * •

Interpretability: One of the challenges of ML-based fetal health
classification is interpretability. ML models are often black boxes, which
means that it can be difficult to understand why they make the predictions
that they do. This can make it difficult to trust ML models and to use them in
clinical practice.

  * •

Regulation: ML-based fetal health classification is a relatively new area, and
there are currently no regulations governing the use of ML models for this
purpose. This could lead to concerns about the safety and efficacy of ML
models for fetal health classification.

###  VI-C Future Work

  * •

Data collection: Future work in the field of ML-based fetal health
classification should focus on collecting more data. This data should be of
high quality and should be representative of the population of pregnant women.

  * •

Data cleaning and preprocessing: Future work should also focus on cleaning and
preprocessing the data. This will help to improve the accuracy of ML models.

  * •

Model development: Future work should focus on developing more accurate and
interpretable ML models. This could be done by using different ML algorithms
or by incorporating additional features into the models.

  * •

Evaluation: Future work should focus on evaluating the performance of ML
models in clinical settings. This will help to ensure that the models are safe
and effective.

  * •

Regulation: Future work should also focus on developing regulations for the
use of ML models for fetal health classification. This will help to ensure
that the models are safe and effective.

Overall, ML has the potential to revolutionize the way that fetal health is
assessed and managed. However, there are a number of limitations, challenges,
and future work that need to be addressed before ML can be widely used in
clinical practice.

##  VII Conclusion

In conclusion, the results of this study suggest that the LightGBM model is a
promising tool for fetal health classification. The model’s high accuracy,
generalizability, and sensitivity to potential abnormalities suggest that it
could be used to improve the early detection and management of fetal health
problems. However, there are a number of limitations, challenges, and future
work that need to be addressed before ML can be widely used in clinical
practice. These include the need for more data, the need to develop more
accurate and interpretable models, and the need to develop regulations for the
use of ML models for fetal health classification. Despite these limitations,
the potential benefits of ML for fetal health classification are significant.
ML models have the potential to provide a more objective and accurate
assessment of fetal health, which could lead to earlier detection and
intervention of fetal health problems. This could improve outcomes for both
mothers and babies. Future research in this area should focus on addressing
the limitations and challenges that have been identified. This could lead to
the development of ML models that are more accurate, interpretable, and
reliable. This could revolutionize the way that fetal health is assessed and
managed, and could improve outcomes for both mothers and babies.

##  VIII Implementation and Dataset

In this research paper, we not only present our findings and results but also
provide the implementation code and dataset used for the experiments. This
allows researchers and practitioners to reproduce our results, validate our
methodology, and further explore the proposed approach.

The code and dataset used in this study are available at [4] and [5]
respectively. The code is written in Python and the dataset is in CSV format.
The code is well-documented and easy to follow. The dataset is large and
diverse, and it includes a variety of features that can be used to train and
evaluate ML models for fetal health classification.

We encourage other researchers to use the code and dataset to reproduce our
results and to develop new ML models for fetal health classification. We
believe that these resources will be valuable to the research community and
will help to advance the field of ML-based fetal health classification.

## References

  * [1] Wang, J., Zhang, J., & Zhang, X. (2016). Fetal health classification using support vector machine. In 2016 IEEE 13th International Conference on Bioinformatics and Biomedicine (pp. 1-6). IEEE.
  * [2] Chen, Y., Wang, Y., & Zhang, L. (2017). Fetal health classification using decision tree algorithm. In 2017 IEEE 14th International Conference on Bioinformatics and Biomedicine (pp. 1-6). IEEE.
  * [3] Zhang, X., Wang, J., & Zhang, X. (2018). Fetal health classification using deep learning. In 2018 IEEE 15th International Conference on Bioinformatics and Biomedicine (pp. 1-6). IEEE.
  * [4] Ayres-de-Campos, D., Bernardes, J., Garrido, A., Marques-de-Sá, J., & Pereira-Leite, L. (2000). Sisporto 2.0: A program for automated analysis of cardiotocograms. J. Matern. Fetal Med., 9(5), 311-318. https://doi.org/10.1002/1520-6661(200009/10)9:5¡311::AID-MFM12¿3.0.CO;2-9
  * [5] Kaggle Code: Fetal Health Classification. (n.d.). Retrieved from https://www.kaggle.com/code/sujithmandala/fetal-health-classification-lightgbm-98-31-acc/notebook/Fetal-Health-Classification


Department of Computer Science and Engineering, Indian Institute of Technology
Roorkee<EMAIL_ADDRESS>Department of Computer Science and
Engineering, Indian Institute of Technology Roorkee,
<EMAIL_ADDRESS>Department of Computer Science and Engineering,
Indian Institute of Technology Roorkee<EMAIL_ADDRESS>Department of Computer Science and Engineering, Indian Institute of Technology
Roorkee, Indiashahbaz.khan@cs.iitr.ac.inhttps://orcid.org/0000-0001-9352-0088
Saumya Talera, Parth Bansal, Shabnam Khan, and Shahbaz Khan [100]General and
reference Empirical studies [100]General and reference Performance
[100]General and reference Experimentation [500]General and reference
Performance [100]General and reference Empirical studies [300]Theory of
computation Pattern matching [300]Theory of computation Data compression
[500]Mathematics of computing Trees [300]Applied computing Bioinformatics
[300]Applied computing Computational genomics
https://github.com/renauga/hogStartup Research Grant SRG/2022/000801 by DST
SERB, Government of India. John Q. Open and Joan R. Access 2 42nd Conference
on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016
Little Whinging, United Kingdom 42 23

# Practical algorithms for Hierarchical overlap graphs

Saumya Talera  Parth Bansal  Shabnam Khan  Shahbaz Khan

###### Abstract

One of the most prominent problems studied in bioinformatics is genome
assembly, where, given a set of overlapping substrings of a source string, the
aim is to compute the source string. Most classical approaches to genome
assembly use assembly graphs built using this set of substrings to compute the
source string efficiently. Prominent such graphs present a tradeoff between
scalability and avoiding information loss. The space efficient (hence
scalable) de Bruijn graphs come at the price of losing crucial overlap
information. On the other hand, complete overlap information is maintained by
overlap graphs at the expense of quadratic space. Hierarchical overlap graphs
were introduced by Cazaux and Rivals [IPL20] to overcome these limitations,
i.e., avoiding information loss despite using linear space. However, their
algorithm required superlinear space and time. After a series of suboptimal
improvements, two optimal algorithms were simultaneously presented by Khan
[CPM2021] and Park et al. [CPM2021], where only the former was seemingly
practical.

We empirically analyze all the practical algorithms for computing Hierarchical
overlap graphs, where the optimal algorithm [CPM2021] outperforms the previous
algorithms as expected. However, it is still based on non-intuitive arguments
for its formal proof and use of non-trivial data structures for its
implementation. We present arguably the most intuitive algorithm, which is
also optimal and uses only elementary arrays for its implementation. Despite
the superior performance of optimal algorithm [CPM2021] over previous
algorithms it comes at the expense of extra memory. Our algorithm empirically
proves even better for both time and memory over all the algorithms,
highlighting its significance in both theory and practice.

We further explore the applications of hierarchical overlap graphs to solve
various forms of suffix-prefix queries on a set of strings. Loukides et al.
[CPM2023] recently presented state-of-the-art algorithms for these queries.
However, these algorithms require complex black-box data structures and are
seemingly impractical. Our algorithm, despite failing to match the state-of-
the-art algorithms theoretically, answer different queries ranging from
$0.01-100$ milliseconds for a data set having around a billion characters.

###### keywords:

Hierarchical Overlap Graphs, String algorithms, Genome assembly

###### category:

##  1 Introduction

Genome assembly is one of the most fundamental problems in Bioinformatics. For
a source string (genome), practical limitations allow sequencing of only a
collection of its substrings (reads) instead of the whole string. Thus, genome
assembly aims to reconstruct the source genome using the sequenced reads. This
is possible only because the sequencing ensures coverage of the entire string
so that we find sufficient overlap among the substrings. This overlap
information plays a fundamental role in solving the genome assembly problem.
In most practical approaches [28, 3, 18, 2, 23, 24], this overlap information
is efficiently processed by representing the substrings in the form of
assembly graphs, such as de Bruijn graphs [22] and overlap graphs (or string
graphs [17]). The de Bruijn graphs present a fundamental trade-off of
achieving scalability (space efficiency) at the expense of loss in overlap
information. This is possible by considering all possible substrings (k-mers)
of the reads having length $k$, and storing the limited overlap information
amongst them, thereby ensuring linear space. On the other hand, overlap graphs
store the maximum overlap between every pair of reads explicitly, thereby
requiring quadratic size, making them impractical for large data sets.

Hierarchical Overlap Graphs (HOG) were formally introduced by Cazaux and
Rivals [6] as an alternative to overcome the limitations of the existing
assembly graphs, maintaining the complete overlap information implicitly using
optimal space (linear). HOG has nodes corresponding to the original substrings
and the maximum overlap between every pair of these substrings. Notably, the
linear size of HOG (despite storing the complete overlap information)
highlights the redundancy of data stored in overlap graphs. Several
applications of HOG have been formerly studied in [5, 4]. For a given set $P$
of $k$ strings with total length $n$, they [6] compute the HOG in $O(n+k^{2})$
time. Moreover, they required superlinear space for this computation. Later,
Park et al. [21] presented an algorithm requiring $O(n\log k)$ time and linear
space. However, they assumed the character set of the strings to be of
constant size. Finally, Khan [10] and Park et al. [20] independently presented
optimal algorithms for computing the HOG in $O(n)$ time. While the former
algorithm only used standard data structures (as lists, stacks), the latter
reduced the problem to that of computing borders [11] requiring complex black
box computations, which itself is a well studied string problem having several
practical approaches under different contexts, thus, its complete evaluation
is beyond the scope of this paper.

Related Work. All the above algorithms, in theory, remove the non-essential
nodes from an AC Trie [1]. In practice, they can use an intermediate Extended
HOG (EHOG) to reduce the memory requirement for these algorithms. Thus, the
fundamental problem is marking those nodes of an AC Trie (or EHOG), which
represent the set of maximum overlaps between every ordered pair of strings in
$P$. This is a special case of the All Pairs Suffix Prefix (APSP) problem,
which reports the maximum overlap corresponding to every ordered pair of
strings. Gusfield et al. [8] optimally solved this classical problem in
$O(n+k^{2})$ time and $O(n)$ space using generalized suffix tree [27]. Later,
other optimal algorithms were presented using generalized suffix array [16]
([19, 25]) and Aho Corasick automaton [1] ([13]). Moreover, in practice,
several algorithms having suboptimal bounds such as Readjoiner [7], SOF [9],
and a recent algorithm by Lin and Park [12], have far superior performance for
APSP, demonstrating the stark difference between theory and practice. Thus,
any empirical analysis cannot trivially overlook the suboptimal algorithms.
Note that since the APSP problem explicitly reports the maximum overlap for
each of the $k^{2}$ ordered pair of strings, the above bound is optimal.
However, when only the set of maximum overlaps is required (as in the case of
HOG), the $O(k^{2})$ factor proves suboptimal.

Recently, Loukides et al. [14] have studied several practically relevant
variants of the APSP problem and presented state-of-the-art algorithms for the
same. However, most of these algorithms involve complex black-box data
structures, making them seemingly impractical. Another interesting variant of
the APSP problem was solved by Ukkonen [26], which reports all pairwise
overlaps (not just maximum) in the decreasing order of their lengths. Notably,
this problem can be solved by EHOG by reporting the internal nodes from the
bottom up.

###  1.1 Our Results

Our results can be succinctly outlined as follows.

  1. 1.

Novel optimal algorithm for HOG. We present arguably the most intuitive
algorithm, which is also optimal. Despite the simplicity of the existing
optimal algorithms, it still uses a non-intuitive approach and non-trivial
data structures for its implementation, whereas our algorithm uses only
elementary arrays.

  2. 2.

Empirical evaluation of practical HOG algorithms. We analyzed all the
seemingly practical algorithms on random and real datasets. On real datasets,
the previous optimal algorithm improves the other algorithms by
$1.3$-$8\times$ using $1.5$-$6\times$ more memory. However, the proposed
optimal algorithm improves the best time by $2.3-5$ and memory by $\approx
1.5\times$. The relative performances improve with the size of the dataset. On
random datasets having $\leavevmode\nobreak\ 10^{5}$ strings with a total
length of $10^{7}$, the optimal algorithm improves the previous state of the
art by over $1.5-2.5\times$ times, while our algorithm improves the optimal by
$\leavevmode\nobreak\ 5\times$. Further, we find that the performance mainly
depends on an intermediately computed EHOG used by all the algorithms. Our
results prove that the proposed algorithm performs superior to the previous
algorithms on both random and real datasets, highlighting its significance in
both theory and practice.

  3. 3.

Applications of HOG. We also explore the applications of hierarchical overlap
graphs to solve various variants of suffix-prefix queries on a set of strings.
Despite the algorithms not matching the state of the art [14] which require
complex black-box data structures, our algorithm require $0.01-100$ ms for all
queries on a data set of a billion characters.

Outline of the paper. We first describe the basic notations and definitions
used throughout the paper in Section 2. In Section 3, we briefly describe the
previous results, highlighting the aspects affecting practical performance.
This is followed by describing our proposed algorithm in Section 4. Then, in
Section 5, we present the experimental setup and evaluation of the practical
algorithms on real and random datasets, justifying the observations using
further evaluation. Section 6 discussed some applications of HOG on variants
of APSP queries. We finally present the conclusions and scope of future work
in Section 7.

##  2 Preliminaries

We are given a set $P=\\{p_{1},p_{2},...p_{k}\\}$ of $k$ non-empty strings
over a finite-set alphabet. The length of a string $p_{i}$ is denoted by
$|p_{i}|$. Let the total length of all strings $p_{i}\in P$ be $n$ ($\geq k$
as non-empty strings). An empty string is denoted by $\epsilon$. A substring
of a string $p$ starting from the first character of $p$ is a prefix of $p$,
while a substring ending at the last character of $p$ is known as a suffix of
$p$. A prefix or suffix of $p$ is called proper if it is not the same as $p$.
For an ordered pair $(p,q)$, an $overlap$ is a string that is both a proper
suffix of $p$ and a proper prefix of $q$, and $ov(p,q)$ denotes the longest
such overlap. We denote $Ov(P)$ as the set of $ov(p_{i},p_{j})$ for all
$p_{i},p_{j}\in P$. We now use the above definition to define the HOG.

For a given $P$, the ACT $\cal{A}$, EHOG $\cal{E}$, and HOG $\cal{H}$ are
defined using different vertex sets as follows. The vertices of $\cal A$ are
all possible prefixes of the strings in $P$ (hence including $P$ and
$\epsilon$). The vertices of $\cal E$ are $P\cup\\{\epsilon\\}$ and all
possible (not necessarily maximum) overlaps of strings in $P$. The vertices of
$\cal H$ are further restricted to the maximum overlaps $Ov(P)\cup
P\cup\\{\epsilon\\}$. Hence for a given $P$, $V({\cal H})\subseteq V({\cal
E})\subseteq V({\cal A})$. For all the above, we add the following types of
edges: (a) Tree edges $(y,x)$ with label $x\setminus y$, for all $x\in V$
where $y$ is the longest proper prefix of $y$ in $V$, and (b) Suffix links
$(x,y)$ with label $x\setminus y$, for all $x\in V$ where $y$ is the longest
proper suffix of $x$ in $V$. See Figure 1 for examples of the same. Also, for
each of the structures the number of nodes are $O(n)$.

We abuse the notation to interchangeably refer to a node as a string
(corresponding to it) and vice-versa. The name tree edges allows us to abuse
the notation and treat each of $\cal A,E$ and $\cal H$ as a tree with
additional suffix links. This makes the outgoing tree edge neighbors of a node
its children, which extends to the notion of descendants and ancestors. This
also makes the leaves of the tree a subset of $P$, the empty string $\epsilon$
as the root, and the remaining strings as internal nodes. Note that some
string $p_{i}\in P$ can also be an internal node if it is a prefix of some
other string $p_{j}\in P$, which is why leaves of the tree are not the same as
$P$. Further, starting from every node $p_{i}\in P$ and following the suffix
links until we reach the root gives us the suffix path of $p_{i}$. We further
have the following property.

Figure 1: The structures ${\cal A}$, ${\cal E}$ and ${\cal H}$ for
$P=\\{aabaa,aadbd,dbdaa\\}$ (figure reproduced from [10]).

######  Lemma 2.1 (HOG Property [8]).

An internal node $v$ in $\cal{A}$ of $P$, is $ov(p_{i},p_{j})$ for two strings
$p_{i},p_{j}\in P$ iff $v$ is an overlap of $(p_{i},p_{j})$ and no descendant
of $v$ is an overlap of $(p_{i},p_{j})$.

##  3 Previous work

We now describe the relevant previous results related to the computation of
HOG. For a given set of strings $P$, the ACT [1] can be computed in linear
time and space. The classical algorithm builds a Trie and adds the suffix
links efficiently using dynamic programming. EHOG [6] can be computed by
simply traversing the suffix path of every string in $P$ in linear time, and
removing the untraversed vertices. The corresponding labels of tree edges, and
suffix links with its labels are also updated simultaneously.

Given an ACT (or EHOG) of $P$, its HOG can be constructed by removing the
nodes that do not satisfy the criterion in Lemma 2.1. We again update the edge
labels and suffix links in linear time as described above. Various approaches
for computing $Ov(P)$ are as follows.

  1. 1.

Cazaux and Rivals [6] requiring $O(n+k^{2})$ time. This algorithm computes a
list $R_{l}(u)$ containing all leaves having ${u}$ as its suffix by traversing
over all suffix paths. A bit vector maintains for each internal node $x$, the
strings in $P$ having overlaps in the descendants of $x$. The bit vector can
be updated in a bottom-up fashion, and compared with $R_{l}(u)$ to decide
whether $u$ is added to $\cal H$. Along with suboptimal time, it also uses
super linear space seemingly limiting its scalability.

  2. 2.

Park et al. [21] requiring $O(n\log k)$ time.  This algorithm sorts the
strings in ${P}$ lexicographically, which makes a contiguous set of leaves the
descendant of each internal node. This allows them to use the practical
segment tree data structure allowing update over an interval of in $O(\log k)$
time. For each node in the suffix path of $p_{i}\in P$, they simply count the
number of descendant leaves (eligible prefixes) which are not covered by a
larger prefix of $p_{i}$. This allows them to process each node of every
suffix path (total $O(n)$) in a single segment tree query and update though
requiring linear space.

  3. 3.

Khan [10] requiring $O(n)$ time. This algorithm also computes $R_{l}(u)$ as in
[6] (referred as ${\cal{L}}_{u}$) and performs a traversal of $\cal{A}$ which
maintains the lowest internal node having each $p\in P$ as a suffix. On
reaching the leaves all such internal nodes are maximum overlaps for the
string representing the leaves. They primarily use stacks and lists for their
implementation.

  4. 4.

Park et al. [20] requiring $O(n)$ time. The algorithm computes the overlaps by
reducing the problem to that of computing borders [11]. Given that the
subproblem itself is a well studied string problem having several practical
approaches under different contexts, its complete evaluation is beyond the
scope of this paper.

Note that except for the last algorithm [20], all the algorithms use simple
and self-contained data structures as vectors, stacks, lists, segment trees,
etc., making them promising for use in our practical evaluation.

##  4 Proposed Algorithm

As described in Section 3, all the algorithms essentially mark the nodes
$Ov(P)$ of $\cal A$ (or $\cal E$), which will be added to $\cal H$, followed
by a single traversal [10] to generate $\cal H$. We thus focus here on
optimally computing this $in{\cal H}$ array. We describe the algorithm
incrementally, firstly to mark all overlaps for all pairs $(p_{i},p_{j})$ for
a fixed $p_{i}$ and all $p_{j}\in P$, secondly optimize it to require
$O(|p_{i}|)$ time after initialization, and finally generalize it to find
$Ov(P)$ in $O(n)$ time. Let us first recall an essential property of HOG that
we use here.

See 2.1

Remark. For the sake of simplicity, we assume no string in $P$ is a prefix of
another, making the nodes in $P$ be the leaves of $\cal A$. We shall later
address how to handle this case separately.

###  4.1 Marking all overlaps $ov(p_{i},*)$ for a string $p_{i}$

Recall that the suffix path of $p_{i}$ visits all the overlaps of $p_{i}$ in
decreasing order of depth. Further, an internal node $x$ on this path can be
overlap of $(p_{i},p_{j})$ only if $p_{j}$ is a descendant of $x$ (as $x$ is a
prefix of its descendants). Hence, for all the internal nodes which are
overlaps for $(p_{i},p_{j})$, the node visited first would be
$ov(p_{i},p_{j})$. Given the above properties, we propose the following simple
process by colouring the leaves from white to black as follows.

Starting with all the leaves white, for every node $x$ on the suffix path of
$p_{i}$, we blacken all the white leaves in $x$’s subtree, marking $x$ if any
leaf was blackened while processing $x$.

The correctness of the above algorithm is evident as $x$’s are visited bottom
up along the suffix path, and only the leaves $p_{j}$ in subtree of $x$ can
have $x$ as an overlap of $(p_{i},p_{j})$.

foreach  _node $v\in V({\cal A})$_ do $in{\cal H}[i]\leftarrow false$;

$in{\cal H}[root]\leftarrow true$;

foreach  _node $v\in V({\cal A})$_ do $count[v]\leftarrow$ Number of children
of $v$ in tree ${\cal A}$;

foreach  _node $x$ in $P$_ do

$in{\cal H}[x]\leftarrow true$;

$v\leftarrow$ Suffix link of $x$;

$V_{m}\leftarrow\emptyset$;

while  _$v\neq root$_ do

if  _$count[favDesc[v]]\neq 0$_ then

$in{\cal H}[v]\leftarrow true$;

$u\leftarrow favDesc[v]$;

while  _$u\neq root$_ do

Add $u$ to $V_{m}$;

if  _$u\neq favDesc[v]$_ then

$count[u]\leftarrow count[u]-1$;

if  _$count[u] >0$_ then break;

else $count[u]\leftarrow 0$;

$u\leftarrow favPAnc[u]$;

$v\leftarrow$ Suffix link of $v$;

foreach  _node $v\in V_{m}$_ do $count[v]\leftarrow$ Number of children of $v$
in tree $\cal A$;

return $in{\cal H}$;

Algorithm 1 $Compute{\cal H}({\cal A})$

###  4.2 Optimally marking $ov(p_{i},*)$ for a string $p_{i}$

Clearly, visiting all descendants repeatedly is inefficient. The main idea
behind the optimization is to lazily blacken the entire subtree of each $x$ in
constant time. This is possible since future updates and queries about
blackened vertices (due to other $x^{\prime}$ further along the suffix path)
will only occur at higher levels than $x$, avoiding direct queries to $x$’s
descendants.

However, to limit the number of updates to constant, we face another issue due
to paths having nodes with single child (see Figure 1). We circumvent it by
maintaining such an entire path using its favoured descendant, where we refer
to nodes having multiple children as favoured. Note a favoured vertex is its
own favoured descendant. The entire path having the same favoured descendant
can be represented together because the number of white leaves of every node
in such a path would always be the same.

We thus maintain the following data to use the above approach efficiently.

  * •

$count[x]:$ Number of child subtrees of $x$ having white leaves.

  * •

$favPAnc[x]:$ The closest proper ancestor of $x$ having multiple children.

  * •

$favDesc[x]:$ The closest descendant of $x$ (not necessarily proper) having
multiple children.

  * •

$V_{m}:$ List of vertices whose $count[\cdot]$ is modified while visiting a
suffix path.

#### Initialization

Initially, since all the leaves are white, we initialize $V_{m}=\emptyset$ and
$count[x]$ as the number of children of $x$ in the tree $\cal A$. Clearly,
using a single traversal over the tree ${\cal A}$, we can initialize
$count[\cdot]$, $favPAnc[\cdot]$ and $favDesc[\cdot]$ in $O(n)$ time.

#### Processing Suffix path of $p_{i}$

Now, starting from the suffix of $p_{i}$ in ${\cal A}$, we process each node
$x$ on the suffix path in order. The process of blackening all the leaves of
the subtree of $x$ can be performed lazily because the future nodes on the
suffix path of $p_{i}$ cannot be the descendants of $x$. Assuming the data
structure is correctly maintained, the $x$ is marked in $in{\cal H}$ if
$count[x]\neq 0$, implying that leaves can be blackened while processing $x$
(recall simplified algorithm). To blacken all the leaves in the subtree of $x$
we set the count of its representative (nodes having a single child in a path
are equivalent) $favDesc[x]$ to zero. Recall that the suffix path of $p_{i}$
is processed in the decreasing order of depth, hence we don’t need to update
the count of any other descendant of $x$. Further, the entire data structure
can be updated by updating the count of the ancestors of $x$ whose $count$ is
affected. Clearly, this includes all the ancestors of $y$ having a subtree
containing white leaves only among the descendants of $x$. These ancestors can
be accessed by repeatedly reducing counts of favoured proper ancestors until
some ancestor has other white leaves remaining in its other subtrees.

#### Analysis

For each $x$ on the suffix path of $p_{i}\in P$, except for repeatedly
updating the $count$ of the favoured proper ancestors, all the other
operations require constant time. We may have to process multiple such
ancestors $y$ whose $count$ became zero, and at most one such ancestor $y^{*}$
whose $count$ remained non-zero. We thus use an amortized analysis argument by
associating twice the cost of processing the ancestor $y^{*}$, which pays off
for its future processing when $count[y^{*}]$ will become zero. Since every
favoured proper ancestor $y$ initially has $count[y]\geq 2$, every $y$ whose
$count[y]$ became zero was once the unique $y^{\prime*}$ while processing
$x^{\prime}$ on the suffix path which made $count[y^{\prime*}]=count[y]=1$,
and hence paid in advance for current cost. Thus, for each $x$ along the
suffix path we process an amortized $O(1)$ favoured proper ancestors in $O(1)$
time. Hence, computing all $ov(p_{i},*)$ for a $p_{i}\in P$ require
$O(|p_{i}|)$ time after initialization of data structures in $O(n)$.

###  4.3 Final Algorithm

The final algorithm requires repeating the above algorithm for each $p_{i}\in
P$. Note that both $favPAnc[\cdot]$ and $favDesc[\cdot]$ are not updated
throughout the algorithm. In order to initialize $count[\cdot]$ efficiently,
we simply maintain a list $V_{m}$ of all the nodes with modified
$count[\cdot]$ for each $x$ on the suffix path, which can be used to restore
$count[\cdot]$ efficiently.

The time taken after initialization by an iteration processing $p_{i}$ is
$O(|p_{i}|)$, we also have $V_{m}=O(|p_{i}|)$ and hence the data structures
can be restored in $O(|p_{i}|)$. Thus, after initialization of data structures
in $O(n)$ time, the time required by the algorithm is $\sum_{p_{i}\in
P}|p_{i}|=O(n)$.

Remark: The case of a string $p_{i}\in P$ being a prefix of another in $P$ can
be handled as follows. Clearly, despite not being a leaf of the tree $\cal A$,
the simple algorithm may blacken it. Hence, on including $p_{i}$ the effective
$count$ of the parent of $p_{i}$ differs from that of its favoured descendant.
Thus, each such $p_{i}\in P$ can be accounted for in the above algorithm
simply by increasing the count of its parent in $\cal A$ and treating it as
favoured.

##  5 Experimental Evaluation

We now evaluate the most promising algorithms for computing HOG in practice.
Since the performance of these algorithms is strongly dependent on the
underlying dataset, we evaluate these algorithms on both real and randomly
generated datasets. Further, given the underlying application of HOG in
bioinformatics, our real datasets were sources from EST datasets that were
previously used the evaluation of algorithms solving APSP [9, 12]. Also, given
the dependence of the complexity of various algorithms on $n$ and $k$, our
generated random datasets helps evaluate this dependence by varying over these
parameters.

###  5.1 Algorithms

The following algorithms were found promising (see Section 3) for evaluation
in practice.

  1. 1.

CazauxR: The simplest algorithm by Cazaux and Rivals[6] requiring $O(n+k^{2})$
time.

  2. 2.

ParkCPR: The improved algorithm by Park et al. [21] requiring $O(n\log k)$
time.

  3. 3.

Khan: The optimal algorithm by Khan [10] requiring $O(n)$ time.

  4. 4.

New: Our proposed algorithm requiring $O(n)$ time.

We followed the approach described in previous results [10], that it is better
to first build an $\cal E$ from $\cal A$, and then use it to build $\cal H$
instead of directly building $\cal H$ using $\cal A$.

###  5.2 Performance measures and Environment

Since all the algorithms compute HOG, which is unique for a given set of
strings $P$, the only relevant parameters evaluated are the time and memory.
All the algorithms were implemented in C++ with g++ compiler (v9.4.0) and use
$-O3$ optimization flag. The performances were evaluated on two different
machines as the real datasets required larger memory. The random database
testing was performed on an Intel(R) Xeon(R) Gold 5117 CPU having 56 cores and
64GB RAM running Linux Ubuntu 20.04.1. The real database testing was performed
on an AMD Ryzen 9 7950X3D 16-Core Processor having 32 cores and 128 GB RAM
running Linux Ubuntu 20.04.6 LTS.

###  5.3 Datasets

The algorithms’ performance primarily depends on the parameters $n$ and $k$.
However, on further exploration, the relative size of underlying ACT, EHOG and
HOG generated were also seemingly significant. The algorithms were evaluated
on the following datasets:

  1. 1.

Real data. We used the complete EST datasets (over alphabets {A, G, C, T}) of
Citrus clementina111http://www.citrusgenomedb.org/, Citrus
sinensis222http://www.citrusgenomedb.org/, Citrus
trifoliata2333http://www.citrusgenomedb.org/ and C. elegans444http://www.uni-
ulm.de/in/theo/research/seqana removing some low-quality reads (containing
other characters). These datasets were previously used for the evaluation of
APSP algorithms [9, 12]. We additionally considered larger datasets on the
genome assemblies of bacterial
organisms555http://ccb.jhu.edu/gage_b/datasets/index.html, which was
previously used for evaluation of genome assemblers [15]. See Table 1 for a
brief description of the datasets. As described later, the performance of the
algorithm additionally depends on the sizes of $\cal A,\cal E$, and $\cal H$,
which are presented to give a complete picture.

  2. 2.

Random data. Given the dependence of the algorithms on the parameters $n$ and
$k$, we consider random datasets generated using two different approaches. We
first fixed the value of $n=10^{7}$ and generated different datasets randomly
for increasing values of $k$. We then fixed the value of $k=10^{5}$, and
generated different data sets randomly for increasing values of $n$. Thus, the
datasets allow us to evaluate the performance of the algorithms with respect
to each parameter, keeping the other as constant.

Dataset | $k$ | $n$ | $|\cal A|$ | $|\cal E|$ | $|\cal H|$
---|---|---|---|---|---
trifoliata | 49.2K | 36.2M | 33.8M | 86.764K | 86.709K
clementina | 104.6K | 91.2M | 62.7M | 201.189K | 201.023K
sinensis | 151.9K | 107.3M | 101.0M | 311.208K | 311.014K
elegans | 206.5K | 108.3M | 81.0M | 867.630K | 867.618K
R_sphaeroides_M | 1.5M | 208.1M | 173.4M | 19.716M | 19.715M
V_cholerae_M | 1.6M | 293.2M | 235.8M | 30.610M | 30.609M
M_abscessus_M | 2.0M | 332.5M | 250.8M | 25.083M | 25.082M
B_cereus_M | 2.1M | 477.9M | 417.6M | 49.119M | 49.117M
V_cholerae_H | 3.9M | 353.7M | 208.1M | 58.798M | 58.798M
M_abscessus_H | 5.5M | 492.4M | 257.5M | 62.039M | 62.038M
S_aureus_H | 7.6M | 741.9M | 363.1M | 220.500M | 220.500M
R_sphaeroides_H | 7.7M | 583.5M | 343.9M | 132.872M | 132.870M
X_axonopodis_H | 11.7M | 1.1B | 614.6M | 281.072M | 281.071M
B_cereus_H | 12.0M | 1.2B | 599.8M | 315.366M | 315.363M
B_fragilis_H | 12.3M | 1.2B | 626.3M | 363.588M | 363.588M
A_hydrophila_H | 13.1M | 1.2B | 642.9M | 376.478M | 376.477M
Table 1: Real datasets from EST and genome assemblies.

###  5.4 Evaluation of real datasets

Dataset | trifoliata | clementina | sinensis | elegans
---|---|---|---|---
$k$ | 49.2K | 104.6K | 151.9K | 206.5K
$n$ | 36.2M | 91.2M | 107.3M | 108.3M
$T(\cal E)$ | 182.00x | 172.50x | 189.33x | 76.67x
CazauxR | Time(s) | 536.428x | 1202.19x | 1993.74x | 3264.26x
Mem | 1.6x | 1.74011x | 1.81526x | 1.69038x
ParkCPR | Time(s) | 24.07x | 22.22x | 26.97x | 17.95x
Mem | 1.77x | 1.87x | 1.96x | 1.68x
Khan | Time(s) | 4.01x | 3.70x | 3.84x | 3.66x
Mem | 5.12x | 5.49x | 5.70x | 3.25x
New | Time(s) | 1x | 1x | 1x | 1x
Mem | 1x | 1x | 1x | 1x
Table 2: EST dataset comparision (for actual performance in Table 5 in Appendix B). Dataset | $k$ | $n$ | $T(\cal E)$ | ParkCPR | Khan | New
---|---|---|---|---|---|---
|  |  | Time | Time | Mem | Time | Mem | Time | Mem
R_sphaeroides_M | 1.5M | 208.1M | 2.50x | 4.38x | 1.53x | 2.50x | 2.00x | 1x | 1x
V_cholerae_M | 1.6M | 293.2M | 3.39x | 4.22x | 1.51x | 2.50x | 1.77x | 1x | 1x
M_abscessus_M | 2.0M | 332.5M | 3.88x | 4.74x | 1.55x | 2.35x | 2.01x | 1x | 1x
B_cereus_M | 2.1M | 477.9M | 3.40x | 3.92x | 1.51x | 2.51x | 1.71x | 1x | 1x
V_cholerae_H | 3.9M | 353.7M | 2.61x | 4.66x | 1.53x | 2.49x | 1.82x | 1x | 1x
M_abscessus_H | 5.5M | 492.4M | 3.02x | 5.06x | 1.55x | 2.55x | 2.00x | 1x | 1x
S_aureus_H | 7.6M | 741.9M | 0.97x | 3.70x | 1.50x | 2.32x | 1.58x | 1x | 1x
R_sphaeroides_H | 7.7M | 583.5M | 1.92x | 4.54x | 1.53x | 2.45x | 1.83x | 1x | 1x
X_axonopodis_H | 11.7M | 1.1B | 2.27x | 3.85x | 1.51x | 2.47x | 1.65x | 1x | 1x
B_cereus_H | 12.0M | 1.2B | 1.77x | 3.95x | 1.51x | 2.39x | 1.61x | 1x | 1x
B_fragilis_H | 12.3M | 1.2B | 1.03x | 3.96x | 1.50x | 2.48x | 1.59x | 1x | 1x
A_hydrophila_H | 13.1M | 1.2B | 1.64x | 3.57x | 1.50x | 2.43x | 1.60x | 1x | 1x
Table 3: Genome Assemblies Datasets Comparison (for actual performance Table 6
in Appendix B)

We evaluate the algorithms on the real datasets described in Table 1. CazauxR
timed out ($\approx 12$hrs) on larger bacterial genome datasets. Hence, its
evaluation is limited to EST datasets. In both the datasets, we first compute
$\cal E$ from the strings in $T(\cal E)$ time, which is used to compute $\cal
H$ by all the algorithms. Note that $T(\cal E)$ is comparable to the running
time of all algorithms when the dataset is large but extremely large for
smaller datasets. This can be explained by comparing the relative sizes of
$\cal A$ and $\cal E$ for EST ($100-300\times$) and bacterial genomes
($1.5-10\times$) as for computing $\cal E$ the input is $\cal A$, while $\cal
H$ is computed using $\cal E$. We also note that the size of $\cal H$ only
slightly improves $\cal E$, which indicates the significance of computing non-
linear algorithms using $\cal E$ (computable linearly) instead of directly
from $\cal A$. The results are shown relative to the best, the actual
performances are added to Appendix B for the sake of completeness.

For the EST datasets (see Table 2), clearly, the proposed algorithm New
performs faster compared to the other algorithm, requiring minimum space as
well. In general, as the size of the dataset increases the relative
performance of CazauxR worsens around $\leavevmode\nobreak\ 500-3000\times$.
On the other hand, the memory requirements are relatively same despite the
super linear space complexity. For both ParkCPR and Khan the relative
performance improves with the size of the dataset. This can be explained by
the argument that as the size of the data increases the impact of the
complexities of data structure involved may decrease. Another factor worth
consideration is the relative memory usage of ParkCPR and Khan, where Khan
required higher memory with respect to ParkCPR and CazauxR, despite improving
the running time. Overall, ParkCPR improves CazauxR by $20-180\times$, while
Khan improves ParkCPR by $6-8\times$ using $3-5\times$ more memory, and New
improves Khan by $3.5-4\times$ in time and all by $1.5\times$ in memory.

For the bacterial genome datasets (see Table 3), again New performs faster
than other algorithms requiring less memory as well. Since CazauxR requires
$>12$hrs it is improved by ParkCPR by at least $100\times$. For both ParkCPR
and Khan, the relative performance (time and memory) again improves with the
size of the dataset, where Khan still requires more memory despite being
closer to ParkCPR. Overall, Khan improves ParkCPR by $1.3-2\times$ at the
expense of slightly more memory, and New improves Khan by $2.3-2.5\times$ also
improving the memory.

On real EST and bacterial genome datasets evaluated we have:

  1. 1.

ParkCPR improves CazauxR by $20$-$180\times$, Khan improves ParkCPR by
$1.3$-$8\times$ using $1.3$-$5\times$ more memory, and New improves Khan in
time by $2.3$-$4\times$ and all in memory by $1.5$-$6\times$.

  2. 2.

With increase in dataset’s size, the relative performances of all algorithms
improve.

###  5.5 Evaluation on random datasets

For the random datasets, we measured the average running time of the
algorithms over several generated strings having the same parameters of $n$
and $k$. The results of the experiments showing the variation of the running
time with respect to $k$ and $n$ are shown in Figure 2.

Figure 2: Variation of running time of the algorithms on the two types of
random datasets

The performance of the algorithms follow similar pattern as real datasets
where New, Khan and ParkCPR are comparable while CazauxR is seemingly
impractical. The performance of ParkCPR is improved by Khan by around
$1.5-2.5\times$, while Khan is improved by New by $\leavevmode\nobreak\
5\times$.

For a fixed value of $n=10^{7}$, as expected CazauxR increases quadratically
with $k$. The other algorithms linearly increase up to $k\leavevmode\nobreak\
8x10^{5}$, then decrease. Recall that ParkCPR had a logarithmic dependence on
$k$, whereas Khan and New are independent of $k$. Given that for such a large
value of $k$, the lengths of individual string becomes closer to $10$, which
my lead to smaller overlaps and hence smaller size of $\cal A,\cal E$ and
$\cal H$. Since the algorithms use the intermediate computation of $\cal E$
for computing $\cal H$, the size of $\cal E$ would greatly affect the
performance of the algorithms.

For a fixed value of $k=10^{5}$, evaluating CazauxR is impractical due to a
direct dependence on $k^{2}$, as was evident from the first experiment. For
the remaining algorithms, we surprisingly see nearly constant performance
irrespective of $n$, which is very surprising because all the algorithms are
linearly dependent on $n$. Again, we believe the size of $\cal E$ shall play a
significant role in explaining this performance. This is because for
completely random strings, the overlap is expected to be very small. Given
that we have only four possible characters in the string $k$ uniformly random
strings may have $\log k$ sized overlap which is independent of $n$. Since $k$
is the dominant factor in the size of $\cal E$, it possibly explains the near-
constant performance of all the algorithms with variation of $n$.

We verify the inference drawn from the above experiments by evaluating the
variation in the size of $\cal E$ for both experiments (see Figure 3). Since
the variation of $\cal E$ closely matches the performance of ParkCPR, Khan and
New, it verifies our inferences that the running times of these algorithms are
strongly dependent on $|\cal E|$ as compared to $n$ or $k$.

Figure 3: Variation of size of EHOG $|\cal E|$ on the two types of random
datasets

On random datasets evaluated under variation of $n$ and $k$ we have:

  1. 1.

Khan improves ParkCPR $1.5-2.5\times$, while New improves Khan by
$\leavevmode\nobreak\ 5\times$.

  2. 2.

The performance of ParkCPR, Khan and New are strongly dependent on $|\cal E|$
instead of $n,k$.

##  6 Applications to APSP variants

We considered various variants of the APSP problem which were recently studied
in [14] giving state of the art theoretical algorithms. However, most of these
algorithms required complex black-box algorithms/data structures for its
implementation. We then formulated simple solutions for the same problems
using HOG (see Appendix A). Despite failing to match the state-of-the-art
algorithms [14] theoretically by a large margin, our algoirhtms performed well
in practice (see Table 4). In summary, to answer different queries ranging our
algorithms required $0.01-100$ milliseconds for a data set having around a
billion characters.

Dataset | $k$ | $n$ | one-to-one | one-to-all | top | count | report
---|---|---|---|---|---|---|---
A_hydrophila_H | 13081385 | 1235604318 | 0.010 | 95.375 | 34.238 | 8.434 | 10.783
B_cereus_H | 12018488 | 1161420605 | 0.009 | 71.926 | 30.076 | 4.433 | 8.397
B_cereus_M | 2068138 | 477906536 | 0.003 | 8.654 | 4.070 | 0.698 | 0.922
B_fragilis_H | 12317015 | 1198165883 | 0.008 | 74.648 | 30.248 | 4.583 | 6.302
M_abscessus_H | 5507950 | 492353747 | 0.002 | 28.556 | 11.384 | 1.627 | 2.376
M_abscessus_M | 1986962 | 332468005 | 0.002 | 7.945 | 4.026 | 0.656 | 0.883
R_sphaeroides_H | 7727979 | 583472776 | 0.003 | 51.254 | 19.836 | 2.811 | 4.310
R_sphaeroides_M | 1509743 | 208072134 | 0.002 | 5.954 | 2.925 | 0.516 | 0.722
S_aureus_H | 7601994 | 741898249 | 0.005 | 32.004 | 13.138 | 1.832 | 2.729
V_cholerae_H | 3854210 | 353704636 | 0.002 | 15.161 | 6.823 | 1.085 | 1.451
V_cholerae_M | 1577183 | 293246651 | 0.002 | 5.826 | 2.967 | 0.510 | 0.670
X_axonopodis_H | 11669945 | 1096782704 | 0.009 | 76.691 | 30.474 | 5.002 | 7.976
Table 4: Running time (in milli-sec) of queries for genome assemblies
datasets.

##  7 Conclusion

We proposed a new algorithm for computing HOG and performed an empirical
evaluation of all the practical algorithms. While the previous optimal
algorithm [10] improves the other algorithms in time, it comes at the expense
of increased memory usage. Our algorithm improves both time and memory with
respect to all previous algorithms. Moreover, our algorithm is also arguably
more intuitive and easier to implement using elementary data structures. We
also considered some applications of the HOG on variants of the APSP problem
and demonstrated its practicality by showing that it requires acceptable time
despite the large size of the dataset. In the future, faster algorithms based
on HOG for the studied variants of APSP might prove useful. Possibly, the
structure of HOG can result in superior algorithms both theoretically and in
practice.

## References

  * [1] Alfred V. Aho and Margaret J. Corasick.  Efficient string matching: An aid to bibliographic search.  Commun. ACM, 18(6):333–340, 1975.  doi:10.1145/360825.360855.
  * [2] Dmitry Antipov, Anton I. Korobeynikov, Jeffrey S. McLean, and Pavel A. Pevzner.  hybridspades: an algorithm for hybrid assembly of short and long reads.  Bioinform., 32(7):1009–1015, 2016.  doi:10.1093/BIOINFORMATICS/BTV688.
  * [3] Anton Bankevich, Sergey Nurk, Dmitry Antipov, Alexey A. Gurevich, Mikhail Dvorkin, Alexander S. Kulikov, Valery M. Lesin, Sergey I. Nikolenko, Son K. Pham, Andrey D. Prjibelski, Alex Pyshkin, Alexander Sirotkin, Nikolay Vyahhi, Glenn Tesler, Max A. Alekseyev, and Pavel A. Pevzner.  Spades: A new genome assembly algorithm and its applications to single-cell sequencing.  J. Comput. Biol., 19(5):455–477, 2012.  doi:10.1089/CMB.2012.0021.
  * [4] Rodrigo Cánovas, Bastien Cazaux, and Eric Rivals.  The compressed overlap index.  CoRR, abs/1707.05613, 2017.  arXiv:1707.05613.
  * [5] Bastien Cazaux, Rodrigo Cánovas, and Eric Rivals.  Shortest DNA cyclic cover in compressed space.  In Ali Bilgin, Michael W. Marcellin, Joan Serra-Sagristà, and James A. Storer, editors, 2016 Data Compression Conference, DCC 2016, Snowbird, UT, USA, March 30 - April 1, 2016, pages 536–545. IEEE, 2016.  doi:10.1109/DCC.2016.79.
  * [6] Bastien Cazaux and Eric Rivals.  Hierarchical overlap graph.  Inf. Process. Lett., 155, 2020.  doi:10.1016/J.IPL.2019.105862.
  * [7] Giorgio Gonnella and Stefan Kurtz.  Readjoiner: a fast and memory efficient string graph-based sequence assembler.  BMC Bioinform., 13:82, 2012.  doi:10.1186/1471-2105-13-82.
  * [8] Dan Gusfield, Gad M. Landau, and Baruch Schieber.  An efficient algorithm for the all pairs suffix-prefix problem.  Inf. Process. Lett., 41(4):181–185, 1992.  doi:10.1016/0020-0190(92)90176-V.
  * [9] Maan Haj Rachid and Qutaibah Malluhi.  A practical and scalable tool to find overlaps between sequences.  BioMed Research International, 2015:905261, Apr 2015.  doi:10.1155/2015/905261.
  * [10] Shahbaz Khan.  Optimal construction of hierarchical overlap graphs.  In Pawel Gawrychowski and Tatiana Starikovskaya, editors, 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wrocław, Poland, volume 191 of LIPIcs, pages 17:1–17:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPICS.CPM.2021.17.
  * [11] Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt.  Fast pattern matching in strings.  SIAM J. Comput., 6(2):323–350, 1977.  doi:10.1137/0206024.
  * [12] Jihyuk Lim and Kunsoo Park.  A fast algorithm for the all-pairs suffix-prefix problem.  Theor. Comput. Sci., 698:14–24, 2017.  doi:10.1016/J.TCS.2017.07.013.
  * [13] Grigorios Loukides and Solon P. Pissis.  All-pairs suffix/prefix in optimal time using aho-corasick space.  Inf. Process. Lett., 178:106275, 2022.  doi:10.1016/J.IPL.2022.106275.
  * [14] Grigorios Loukides, Solon P. Pissis, Sharma V. Thankachan, and Wiktor Zuba.  Suffix-prefix queries on a dictionary.  In Laurent Bulteau and Zsuzsanna Lipták, editors, 34th Annual Symposium on Combinatorial Pattern Matching, CPM 2023, June 26-28, 2023, Marne-la-Vallée, France, volume 259 of LIPIcs, pages 21:1–21:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPICS.CPM.2023.21.
  * [15] Tanja Magoc, Stephan Pabinger, Stefan Canzar, Xinyue Liu, Qi Su, Daniela Puiu, Luke J. Tallon, and Steven L. Salzberg.  GAGE-B: an evaluation of genome assemblers for bacterial organisms.  Bioinform., 29(14):1718–1725, 2013.  doi:10.1093/BIOINFORMATICS/BTT273.
  * [16] Udi Manber and Eugene W. Myers.  Suffix arrays: A new method for on-line string searches.  SIAM J. Comput., 22(5):935–948, 1993.  doi:10.1137/0222058.
  * [17] Eugene W. Myers.  The fragment assembly string graph.  In ECCB/JBI’05 Proceedings, Fourth European Conference on Computational Biology/Sixth Meeting of the Spanish Bioinformatics Network (Jornadas de BioInformática), Palacio de Congresos, Madrid, Spain, September 28 - October 1, 2005, page 85, 2005.  doi:10.1093/BIOINFORMATICS/BTI1114.
  * [18] Sergey Nurk, Dmitry Meleshko, Anton I. Korobeynikov, and Pavel A. Pevzner.  metaspades: A new versatile de novo metagenomics assembler.  In Mona Singh, editor, Research in Computational Molecular Biology - 20th Annual Conference, RECOMB 2016, Santa Monica, CA, USA, April 17-21, 2016, Proceedings, volume 9649 of Lecture Notes in Computer Science, page 258. Springer, 2016.  URL: https://link.springer.com/content/pdf/bbm%3A978-3-319-31957-5%2F1.pdf.
  * [19] Enno Ohlebusch and Simon Gog.  Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem.  Inf. Process. Lett., 110(3):123–128, 2010.  doi:10.1016/J.IPL.2009.10.015.
  * [20] Sangsoo Park, Sung Gwan Park, Bastien Cazaux, Kunsoo Park, and Eric Rivals.  A linear time algorithm for constructing hierarchical overlap graphs.  In Pawel Gawrychowski and Tatiana Starikovskaya, editors, 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wrocław, Poland, volume 191 of LIPIcs, pages 22:1–22:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPICS.CPM.2021.22.
  * [21] Sung Gwan Park, Bastien Cazaux, Kunsoo Park, and Eric Rivals.  Efficient construction of hierarchical overlap graphs.  In Christina Boucher and Sharma V. Thankachan, editors, String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, volume 12303 of Lecture Notes in Computer Science, pages 277–290. Springer, 2020.  doi:10.1007/978-3-030-59212-7\\_20.
  * [22] P. A. Pevzner.  l-Tuple DNA sequencing: computer analysis.  Journal of Biomolecular Structure & Dynamics, 7(1):63–73, August 1989.
  * [23] Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman.  An eulerian path approach to dna fragment assembly.  Proceedings of the National Academy of Sciences of the United States of America, 98(17):9748–9753, 2001.
  * [24] Jared T. Simpson and Richard Durbin.  Efficient construction of an assembly string graph using the fm-index.  Bioinform., 26(12):367–373, 2010.  doi:10.1093/BIOINFORMATICS/BTQ217.
  * [25] William H. A. Tustumi, Simon Gog, Guilherme P. Telles, and Felipe A. Louza.  An improved algorithm for the all-pairs suffix-prefix problem.  J. Discrete Algorithms, 37:34–43, 2016.  doi:10.1016/J.JDA.2016.04.002.
  * [26] Esko Ukkonen.  A linear-time algorithm for finding approximate shortest common superstrings.  Algorithmica, 5(3):313–323, 1990.  doi:10.1007/BF01840391.
  * [27] Peter Weiner.  Linear pattern matching algorithms.  In 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, pages 1–11. IEEE Computer Society, 1973\.  doi:10.1109/SWAT.1973.13.
  * [28] Daniel R Zerbino and Ewan Birney.  Velvet: algorithms for de novo short read assembly using de bruijn graphs.  Genome research, 18(5):821—829, May 2008.  doi:10.1101/gr.074492.107.

##  Appendix A Applications to String Problems

In this paper, we also consider the variations of the classical all-pairs
suffix-prefix problem (APSP) on a set of strings $P$ described by Loukides et
al. [14].

  * •

$OnetoOne(i,j)$: report the string $ov(p_{i},p_{j})$.

  * •

$OnetoAll(i)$: report $ov(p_{i},p_{j})$ for every $p_{j}\in P$.

  * •

$Report(i,l)$: report all $j\in[1,k]$ where $ov(p_{i},p_{j})\geq l$ for an
integer $l\geq 0$.

  * •

$Count(i,l)$: report the count of all $j\in[1,k]$ where $ov(p_{i},p_{j})\geq
l$ for an integer $l\geq 0$.

  * •

$Top(i,c)$: report all $j\in[1,k]$ corresponding to any $c$ highest values of
$|ov(p_{i},p_{j})|$.

We are given a dictionary $P$ of $k$ strings $p_{1},p_{2},.....p_{k}$ of total
length $n$. For all the queries we assume the given strings are in sorted
order. If the strings are not sorted, we can sort them in $O(||P||)$.

###  A.1 One to One Query

We need to find for given $i$ and $j$, $ov(p_{i},p_{j})$, where
$p_{i},p_{j}\in P$. Each node in HOG has 2 values associated with it - $start$
and $end$. $start$ indicates the minimum index in $[1,k]$ such that the node
is a prefix of $p_{start}$. ${end}$ denotes the maximum index of the same. We
first obtain the node corresponding to the $p_{i}$, then we iterate over the
suffix path of this node, and the first node in which we find $j$ in between
$[start,end]$ is the deepest node which is the prefix of string $p_{j}$ and
also a suffix of string $p_{i}$ so the length corresponding to this node is
the $ov(p_{i},p_{j})$. The number of nodes in the suffix path of a string is
bounded by $k$ and the length of the string $p_{i}$. So, the overall
complexity of this algorithm is $O(min(k,|p_{i}|)$. We can further improve the
time complexity with HOG by using advanced data structure as used in Loukides
et al.[14]. The data structure by Loukides et al. for answering one-to-one
query constructs in $O(n\log{log{n}})$ time while the HOG construct requires
$O(n)$ time. The algorithm by Loukides et al. uses various black box
algorithms, which are very difficult to implement, and ours are very easy to
implement.

Naive | Current Algorithm | With HOG
---|---|---
$O(|p_{i}|+|p_{j}|)$ |  $O({\log{\log{k}}})$ with $O(n)$ space |  $O(min(k,|p_{i}|)$ with $O(n)$ space

###  A.2 One to All Query

We need to find $ov(p_{i},p_{j})$, for every $p_{j}\in P$ for given $p_{i}$.

######  Lemma A.1 ([14]).

Let $u$ and $v$ be two non roots of HOG with labeled intervals
$I_{u}=[start_{u},end_{u}]$ and $I_{v}=[start_{v},end_{v}]$, respectively then
either $[start_{u},end_{u}]$ contains $[start_{v},end_{v}]$ or
$[start_{v},end_{v}]$ contains $[start_{u},end_{u}]$ or $[start_{u},end_{u}]$
and $[start_{v},end_{v}]$ do not intersect.

We iterate over the suffix path of the string $p_{i}$, and for each node, we
only need to update the answer for those strings that have not already been
visited. As we iterate over the suffix path, the node we get will definitely
have a smaller length than the node we already visited. So, we need to update
the answer for only those strings that are visited the first time.

For each string, we maintain the best possible guess of the following not
visited string. Then, when we iterate from $start$ to $end$ indexes of the
current node in HOG, we jump the indexes by the $NextRemaining$ nodes, and at
last, we update the $NextRemaining$ for the $start$ and $end$ indexes. This
will take a total of $O(k)$ time. As we basically jump through the whole range
in $O(1)$ time and we visit the compressed range at most one more time by the
first node that contains this range(Lemma A.1) in the suffix path of $p_{i}$
and at that time we will not traverse this range. We compressed this new range
and will not encounter the former range as the new one will now be contained
by any other node. We achieved the same complexity as Loukides et al., and our
algorithm is very easy to implement. Also, HOG is specially designed for APSP.
The algorithms used by Loukides et al. for APSP are built on some advanced
data structure that answers only the queries for which they are designed.
While HOG can answer various types of queries.

Naive | Current Algorithm | With HOG
---|---|---
$O((k-1)*|p_{i}|+\sum_{j=1}^{k}|p_{J}|)$ |  $O(k)$ with $O(n)$ space |  $O(k)$ with $O(n)$ space

###  A.3 Report Query

We need to output for given $p_{i}$ and $l$ all indexes $j$ such that
$ov(p_{i},p_{j})\geq l$, where $p_{j}\in P$. In this type of query, we are
doing the same as a one-to-all query, except in this, we don’t travel to the
root of the tree; instead, we travel up to the node that has a corresponding
string length greater than equal to $l$.

Naive | Current Algorithm | With HOG
---|---|---
$O((k-1)*|p_{i}|+\sum_{j=1}^{k}|p_{j}|)$ |  $O(\log{n}/\log{\log{n}}+output)$ with $O(n)$ space |  $O(k)$ with $O(n)$ space

###  A.4 Count Query

We need to output for given $p_{i}$ and $l$ number of indexes $j$ such that
$ov(p_{i},p_{j})\geq l$, where $p_{j}\in P$. In this type of query, we are
doing the same as the report query, except we return the count instead of the
whole array.

Naive | Current Algorithm | With HOG
---|---|---
$O((k-1)*|p_{i}|+\sum_{j=1}^{k}|p_{j}|)$ |  $O(\log{n}/\log{\log{n}})$ with $O(n)$ space |  $O(k)$ with $O(n)$ space

###  A.5 Top Query

We need to output for given $p_{i}$ and $c$, $c$ different indexes $j$ with
the highest values of $ov(p_{i},p_{j})$ (tie breaker solved arbitrarily),
where $p_{j}\in P$. In this type of query, we are doing the same as a one-to-
all query, except in this, we don’t travel to the root of the tree; instead,
we stop when we find the answer for $c$ vertices. As we know this is also the
top $c$ strings, which has the highest $ov(p_{i},p_{j})$.

Naive | Current Algorithm | With HOG
---|---|---
$O((k-1)*|p_{i}|+\sum_{j=1}^{k}|p_{j}|)$ |  $O(\log^{2}{n}/\log{\log{n}}+output)$ with $O(n)$ space |  $O(k)$ with $O(n)$ space

###  A.6 Comparisons between state of the art algorithm and our algorithm

We have achieved the same bound as of [14] for one-to-all query and our
algorithm is easier to implement than the state-of-the-art algorithm. Also,
for other queries, there is still room for improvement. Current algorithms
with HOG are easier to implement than [14]. Also, We are able to answer
multiple types of queries with only HOG, while in [14] they have used
different data structures for different types of queries which make them
harder to implement and will practically take more time for construction.
Also, for construction of data structure in one-to-one query use
$O(n\log{\log{n}})$ time while we are constructing HOG in $O(n)$ time.

##  Appendix B Actual performance of algorithms on real datasets

Dataset | trifoliata | clementina | sinensis | elegans
---|---|---|---|---
$k$ | 49.2K | 104.6K | 151.9K | 206.5K
$n$ | 36.2M | 91.2M | 107.3M | 108.3M
$T(\cal E)$ | 1.82 | 3.45 | 5.68 | 4.60
CazauxR | Time(s) | 5.36 | 24.04 | 59.81 | 195.86
Mem | 14.4M | 30.8M | 45.2M | 128.3M
ParkCPR | Time(s) | 0.14 | 0.35 | 0.68 | 1.11
Mem | 15.9M | 33.1M | 48.8M | 127.4M
Khan | Time(s) | 0.02 | 0.06 | 0.10 | 0.23
Mem | 45.9M | 97.3M | 141.9M | 246.5M
New | Time(s) | 0.01 | 0.02 | 0.03 | 0.06
Mem | 9.0M | 17.7M | 24.9M | 75.9M
Table 5: Actual Performance of the algorithms on EST datasets Dataset | $k$ | $n$ | $T(\cal E)$ | ParkCPR | Khan | New
---|---|---|---|---|---|---
|  |  |  | Time(s) | Mem | Time(s) | Mem | Time(s) | Mem
R_sphaeroides_M | 1.5M | 208.1M | 11.38 | 19.92 | 2.7G | 11.36 | 3.5G | 4.55 | 1.8G
V_cholerae_M | 1.6M | 293.2M | 20.82 | 25.94 | 4.2G | 15.38 | 4.9G | 6.15 | 2.8G
M_abscessus_M | 2.0M | 332.5M | 22.05 | 26.91 | 3.5G | 13.36 | 4.5G | 5.68 | 2.3G
B_cereus_M | 2.1M | 477.9M | 34.43 | 39.69 | 6.7G | 25.48 | 7.6G | 10.13 | 4.5G
V_cholerae_H | 3.9M | 353.7M | 33.28 | 59.32 | 8.2G | 31.74 | 9.7G | 12.74 | 5.3G
M_abscessus_H | 5.5M | 492.4M | 42.42 | 71.07 | 8.7G | 35.86 | 11.2G | 14.06 | 5.6G
S_aureus_H | 7.6M | 741.9M | 51.94 | 198.27 | 30.3G | 124.31 | 31.9G | 53.62 | 20.2G
R_sphaeroides_H | 7.7M | 583.5M | 72.57 | 171.16 | 18.5G | 92.24 | 22.1G | 37.70 | 12.1G
X_axonopodis_H | 11.7M | 1.1B | 171.02 | 290.15 | 38.7G | 185.72 | 42.3G | 75.31 | 25.6G
B_cereus_H | 12.0M | 1.2B | 143.08 | 318.72 | 43.4G | 192.78 | 46.5G | 80.69 | 28.8G
B_fragilis_H | 12.3M | 1.2B | 94.93 | 364.64 | 49.9G | 228.30 | 52.8G | 92.09 | 33.2G
A_hydrophila_H | 13.1M | 1.2B | 173.81 | 377.88 | 51.8G | 257.68 | 54.9G | 105.87 | 34.4G
Table 6: Actual Performance of the algorithms on bacterial genome datasets