iFM-index: A Novel FM-Index Based on Machine Learning

Sequence alignment is an increasingly important tool with the generation of large amounts of low-cost sequencing data, and it is typically accelerated by building an index. The FM-index, a well-known compressed full-text index, shows excellent performance for genomic data in practice, but it is limited by space. In the FM-index, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{cc}$</tex> is an auxiliary structure for efficiently calculating the number of occurrences of each character in each position of the reference. However, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{cc}$</tex> takes up the majority of space in the FM-index because its size is proportional to the length of the original reference. One way to reduce space of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{cc}$</tex> is sampling, i.e., storing one row every several rows, but the space overhead is still high. In this paper, we propose <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$i\mathbf{FM}$</tex> -index, an intelligent FM -index that uses a new computational structure based on machine learning to replace <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{cc}$</tex>, For each character in the reference, we build a linear regression model on its <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{cc}$</tex> values. The space overhead of the model is much lower than that of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{cc}$</tex>. When searching for the reads over the reference, iFM-index uses the model to predict the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{cc}$</tex> values, ensuring that the error of each prediction is no greater than a given constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon$</tex> by the segmented model. Our experiments show that replacing <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{cc}$</tex> with a linear regression model can achieve significant space savings, yet still be time-efficient.