Search

In this paper we give an algorithm for streaming k-edit approximate pattern matching which uses space Õ(k²) and time Õ(k²) per arriving symbol. This improves substantially on the recent algorithm of Kociumaka, Porat and Starikovskaya [Kociumaka et al., 2022] which uses space Õ(k⁵) and time Õ(k⁸) per arriving symbol. In the k-edit approximate pattern matching problem we get a pattern P and text T and we want to identify all substrings of the text T that are at edit distance at most k from P. In the streaming version of this problem both the pattern and the text arrive in a streaming fashion symbol by symbol and after each symbol of the text we need to report whether there is a current suffix of the text with edit distance at most k from P. We measure the total space needed by the algorithm and time needed per arriving symbol., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 22:1-22:14

Text-to-pattern distance is a fundamental problem in string matching, where given a pattern of length m and a text of length n, over an integer alphabet, we are asked to compute the distance between pattern and the text at every location. The distance function can be e.g. Hamming distance or 𝓁_p distance for some parameter p > 0. Almost all state-of-the-art exact and approximate algorithms developed in the past ∼ 40 years were using FFT as a black-box. In this work we present 𝒪~(n/ε²) time algorithms for (1±ε)-approximation of 𝓁₂ distances, and 𝒪~(n/ε³) algorithm for approximation of Hamming and 𝓁₁ distances, all without use of FFT. This is independent to the very recent development by Chan et al. [STOC 2020], where 𝒪(n/ε²) algorithm for Hamming distances not using FFT was presented - although their algorithm is much more "combinatorial", our techniques apply to other norms than Hamming., LIPIcs, Vol. 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), pages 29:1-29:11

In pattern matching, a gap constraint is a more flexible wildcard than traditional wildcards “?”and “*”. Pattern matching with gap constraints is more difficult to handle and fulfills user's enquiries more easily. Pattern matching with gap constraints has therefore been carried out in numerous research works, such as music information retrieval, searching protein sites, and sequence pattern mining. Strict pattern matching under a nonoverlapping condition, as a type of pattern matching with gap constraints, is a key issue of sequence pattern mining with gap constraints since it can be used to compute the frequency of a pattern. Exact matching limits the flexibility of the match to some extent since it requires each character to be matched exactly. We therefore address approximate strict pattern matching under the nonoverlapping constraints (ASPNO) and propose an effective algorithm, named NETtree for ASPNO (NETASPNO), which first transforms the problem into a Nettree data structure, an extensive tree structure. To find the nonoverlapping occurrences effectively, we propose the concept of number of roots paths with distance constraints (NRPDC) which indicates the number of path from a node to the roots with distanced and can be used to delete useless parent-child relationships and useless nodes. We iteratively recalculate the NRPDCs of each node on the subnettree with the rightmost root. Then we can get a path from the rightmost leaf to its rightmost root without using the backtracking strategy. NETASPNO therefore iteratively gets the rightmost root-leaf-path and prunes the path on the Nettree. Extensive experimental results demonstrate that NETASPNO has better performance than the other competitive algorithms.

We consider the problem of computing distance between a pattern of length n and all n-length subwords of a text in the streaming model. In the streaming setting, only the Hamming distance (L0) has been studied. It is known that computing the exact Hamming distance between a pattern and a streaming text requires Ω(n) space (folklore). Therefore, to develop sublinear-space solutions, one must relax their requirements. One possibility to do so is to compute only the distances bounded by a threshold k, see [SODA'19, Clifford, Kociumaka, Porat] and references therein. The motivation for this variant of this problem is that we are interested in subwords of the text that are similar to the pattern, i.e. in subwords such that the distance between them and the pattern is relatively small. On the other hand, the main application of the streaming setting is processing large-scale data, such as biological data. Recent advances in hardware technology allow generating such data at a very high speed, but unfortunately, the produced data may contain about 10% of noise [Biol. Direct.'07, Klebanov and Yakovlev]. To analyse such data, it is not sufficient to consider small distances only. A possible workaround for this issue is the (1 ± ε)-approximation. This line of research was initiated in [ICALP'16, Clifford and Starikovskaya] who gave a (1 ± ε)-approximation algorithm with space Oe(ε−5 √n). In this work, we show a suite of new streaming algorithms for computing the Hamming, L1, L2 and general Lp (0 < p < 2) distances between the pattern and the text. Our results significantly extend over the previous result in this setting. In particular, for the Hamming distance and for the Lp distance when 0 < p ≤ 1 we show a streaming algorithm that uses Oe(ε−2 √n) space for polynomial-size alphabets., Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), ISBN:978-3-95977-164-1

The $k$-mismatch problem consists in computing the Hamming distance between a pattern $P$ of length $m$ and every length-$m$ substring of a text $T$ of length $n$, if this distance is no more than $k$. In many real-world applications, any cyclic rotation of $P$ is a relevant pattern, and thus one is interested in computing the minimal distance of every length-$m$ substring of $T$ and any cyclic rotation of $P$. This is the circular pattern matching with $k$ mismatches ($k$-CPM) problem. A multitude of papers have been devoted to solving this problem but, to the best of our knowledge, only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for the $k$-CPM problem. Specifically, we show an $O(nk)$-time algorithm and an $O(n+\frac{n}{m}\,k^4)$-time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the $k$-mismatch problem [Bringmann et al., SODA 2019]. A preliminary version of this work appeared at FCT 2019. In this version we improve the time complexity of the main algorithm from $O(n+\frac{n}{m}\,k^5)$ to $O(n+\frac{n}{m}\,k^4)$., Extended version of a paper from FCT 2019

We show, given a binary integer function diamond that is piecewise polynomial, that (+,diamond) vector products are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include the dominance and l_{2p+1} distances for constant p. Our results imply equivalence (up to polylog factors) between the complexity of computing All Pairs Hamming Distance, All Pairs l_{2p+1} Distance and Dominance Matrix Product, and equivalence between Hamming Distance Pattern Matching, l_{2p+1} Pattern Matching and Less-Than Pattern Matching. The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are likely to be optimal, given lack of progress in improving upper bounds for Hamming distance in the past 30 years. While reductions between selected pairs of products were presented in the past, our work is the first to generalize them to a general class of functions, showing that a wide class of "intermediate" complexity problems are in fact equivalent., Leibniz International Proceedings in Informatics (LIPIcs), 128, ISSN:1868-8969, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), ISBN:978-3-95977-103-0

We consider a generalization of the recently introduced order-preserving pattern matching. The difference between the standard pattern matching and the order-preserving variant is that instead of looking for an exact copy of the pattern, we only require that the relative order between the elements is the same. In our generalization, we additionally allow up to k mismatches between the pattern of length m and the text of length n, and the goal is to construct an efficient algorithm for small values of k. Our solution detects an order-preserving occurrence with up to k mismatches in O(n(loglogm+kloglogk)) time.

Edit distance similarity search, also called approximate pattern matching, is a fundamental problem with widespread database applications. The goal of the problem is to preprocess n strings of length d, to quickly answer queries q of the form: if there is a database string within edit distance r of q, return a database string within edit distance cr of q. Previous approaches to this problem either rely on very large (superconstant) approximation ratios c, or very small search radii r. Outside of a narrow parameter range, these solutions are not competitive with trivially searching through all n strings. In this work we give a simple and easy-to-implement hash function that can quickly answer queries for a wide range of parameters. Specifically, our strategy can answer queries in time Õ(d3^rn^{1/c}). The best known practical results require c ≫ r to achieve any correctness guarantee; meanwhile, the best known theoretical results are very involved and difficult to implement, and require query time that can be loosely bounded below by 24^r. Our results significantly broaden the range of parameters for which there exist nontrivial theoretical bounds, while retaining the practicality of a locality-sensitive hash function., LIPIcs, Vol. 186, 24th International Conference on Database Theory (ICDT 2021), pages 21:1-21:22

Given a text T of length n and a pattern P of length m, the approximate pattern matching problem asks for computation of a particular distance function between P and every m-substring of T. We consider a (1 +/- epsilon) multiplicative approximation variant of this problem, for l_p distance function. In this paper, we describe two (1+epsilon)-approximate algorithms with a runtime of O~(n/epsilon) for all (constant) non-negative values of p. For constant p >= 1 we show a deterministic (1+epsilon)-approximation algorithm. Previously, such run time was known only for the case of l_1 distance, by Gawrychowski and Uznanski [ICALP 2018] and only with a randomized algorithm. For constant 0, Leibniz International Proceedings in Informatics (LIPIcs), 128, ISSN:1868-8969, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), ISBN:978-3-95977-103-0

In this study, we present a new web interface for major bioinformatics algorithms and introduce a novel approximate string matching algorithm. Our web interface executes major algorithms on the field for the use of computational biologists, students or any other interested researchers. In the web interface, algorithms come under three sections: Sequence alignment, pattern matching and motif finding. In each section, we introduce algorithms in order to find best fitting one for specific dataset and problem. The interface introduces execution time, memory usage and context specific results of algorithms such as alignment score. The interface utilizes emerging open source languages and tools. In order to develop light and user-friendly interface, all parts of the interface coded with Python language. On the other hand, Django is used for web interface. Second contribution of the study is novel A-BOM algorithm, which is designed for approximate pattern matching problem. The algorithm is approximate matching variation of Backward Oracle Matching. We compare our algorithm with popular approximate string matching algorithms. Results denote that A-BOM introduces %30 to %80 short runtime improvement when compared to current approximate pattern matching algorithms on long patterns. Bu çalışmada temel biyoinformatik algoritmaları için yeni bir web ara yüzü ve özgün bir yaklaşık desen eşleştirme algoritması sunmaktayız. Web ara yüzümüz biyologlar, öğrenciler ve ilgili araştırmacılar için bu alandaki temel algoritmaları çalıştırmaktadır. Web ara yüzünde algoritmalar üç bölüm altında toplanmaktadır: Dizilim hizalama, desen eşleştirme ve motif bulma. Her bir bölümde, özgül veri seti ve problemlere en iyi uyan algoritmanın bulunabilmesi için sonuçlarını karşılaştırabilecekleri algoritmalar sunulmaktadır. Web ara yüzü çalışma süreleri, hafıza kullanımı ve hizalama skoru gibi konuya özel sonuçları sunmaktadır. Ara yüz yeni geliştirilen açık kaynak kodlu dilleri ve araçları kullanmaktadır. Hafif ve kullanıcı dostu bir ara yüz olması amacıyla ara yüzün tüm kısımları Python dili ile kodlanmıştır. Diğer yandan web ara yüzü için Django kullanılmıştır. Çalışmanın ikinci katkısı, yaklaşık desen eşleştirme için tasarlanmış yeni A-BOM algoritmasıdır. Bu algoritma Backwards Oracle Matching algoritmasının yaklaşık varyasyonudur. Algoritmamızı popüler yaklaşık desen eşleştirme algoritmaları ile kıyasladık. Sonuçlar, A-BOM algoritmasını güncel yaklaşık desen eşleştirme algoritmaları ile uzun desenler üzerinde karşılaştırdığımızda, çalışma süresinde %30 ile %80 arasında kısalma gelişimi olduğunu göstermektedir.

Inthis study, we present a new web interface for major bioinformatics algorithms andintroduce a novel approximate string matching algorithm. Our web interface executesmajor algorithms on the field for the use of computational biologists, studentsor any other interested researchers. In the web interface, algorithms comeunder three sections: Sequence alignment, pattern matching and motif finding. Ineach section, we introduce algorithms in order to find best fitting one forspecific dataset and problem. The interface introduces execution time, memoryusage and context specific results of algorithms such as alignment score. Theinterface utilizes emerging open source languages and tools. In order todevelop light and user-friendly interface, all parts of the interface codedwith Python language. On the other hand, Django is used for web interface. Secondcontribution of the study is novel A-BOM algorithm, which is designed forapproximate pattern matching problem. The algorithm is approximate matching variationof Backward Oracle Matching. We compare our algorithm with popular approximatestring matching algorithms. Results denote that A-BOM introduces %30 to %80 shortruntime improvement when compared to current approximate pattern matching algorithmson long patterns., Bu çalışmada temel biyoinformatik algoritmalarıiçin yeni bir web ara yüzü ve özgün bir yaklaşık desen eşleştirme algoritmasısunmaktayız. Web ara yüzümüz biyologlar, öğrenciler ve ilgili araştırmacılariçin bu alandaki temel algoritmaları çalıştırmaktadır. Web ara yüzündealgoritmalar üç bölüm altında toplanmaktadır: Dizilim hizalama, desen eşleştirmeve motif bulma. Her bir bölümde, özgül veri seti ve problemlere en iyi uyanalgoritmanın bulunabilmesi için sonuçlarını karşılaştırabilecekleri algoritmalarsunulmaktadır. Web ara yüzü çalışma süreleri, hafıza kullanımı ve hizalamaskoru gibi konuya özel sonuçları sunmaktadır. Ara yüz yeni geliştirilen açıkkaynak kodlu dilleri ve araçları kullanmaktadır. Hafif ve kullanıcı dostu birara yüz olması amacıyla ara yüzün tüm kısımları Python dili ile kodlanmıştır.Diğer yandan web ara yüzü için Django kullanılmıştır. Çalışmanın ikincikatkısı, yaklaşık desen eşleştirme için tasarlanmış yeni A-BOM algoritmasıdır.Bu algoritma Backwards Oracle Matching algoritmasının yaklaşık varyasyonudur.Algoritmamızı popüler yaklaşık desen eşleştirme algoritmaları ile kıyasladık. Sonuçlar,A-BOM algoritmasını güncel yaklaşık desen eşleştirme algoritmaları ile uzundesenler üzerinde karşılaştırdığımızda, çalışma süresinde %30 ile %80 arasında kısalmagelişimi olduğunu göstermektedir.

Computing the distance between a given pattern of length n and a text of length m is defined as calculating, for every m-substring of the text, the distance between the pattern and the sub- string. This naturally generalizes the standard notion of exact pattern matching to incorporate dissimilarity score. For both Hamming and L1 distance only relatively slow O(n√m) solutions are known for this generalization. This can be overcome by relaxing the question. For Hamming distance, the usual relaxation is to consider the k-bounded variant, where distances exceeding k are reported as ∞, while for L1 distance asking for a(1±ε)-approximation seems more natural. For k -bounded Hamming distance, Amir et al. [J. Algorithms 2004] showed an O(n√k) time algorithm, and Clifford et al. [SODA 2016] designed an O((m+k2) ·n/m) time solution. We provide a smooth time trade-off between these bounds by exhibiting an O((m+k√m) ·n/m) time algorithm. We complement the trade-off with a matching conditional lower bound, show-ing that a significantly faster combinatorial algorithm is not possible, unless the combinatorial matrix multiplication conjecture fails. We also exhibit a series of reductions that together allow us to achieve essentially the same complexity for k-bounded L1 distance. Finally, for (1±ε)- approximate L1 distance, the running time of the best previously known algorithm of Lipsky and Porat [Algorithmica 2011] was O(ε−2n). We improve this to O(ε−1n), thus essentially matching the complexity of the best known algorithm for (1±ε) -approximate Hamming distance., Leibniz International Proceedings in Informatics (LIPIcs), ISBN:978-3-95977-076-7

This paper revisits the problem of indexing a text S[1..n] for pattern matching with up to k errors. A naive solution either has a worst-case matching time complexity of @W(m^k) or requires @W(n^k) space, where m is the length of the pattern. Devising a solution with better performance has been a challenge until Cole et al. (2004) [5] showed an O(nlog^kn)-space index that can support k-error matching in O(m+occ+log^knloglogn) time, where occ is the number of occurrences. Motivated by the indexing of long sequences like DNA, we have investigated the feasibility of devising a linear-size index that still has a time complexity linear in pattern length. This paper in particular presents an O(n)-space index that supports k-error matching in O(m+occ+(logn)^k^(^k^+^1^)loglogn) worst-case time. This index can be further compressed from O(n) words into O(n) bits with a slight increase in the time complexity.

We present an index that stores a text of length n such that given a pattern of length m, all the substrings of the text that are within Hamming distance (or edit distance) at most k from the pattern are reported in O(m+loglogn+#matches) time (for constant k). The space complexity of the index is O(n1+ϵ) for any constant ϵ>0.

Historically, approximate pattern matching has mainly focused at coping with errors in the data, while the order of the text/pattern was assumed to be more or less correct. In this paper we consider a class of pattern matching problems where the content is assumed to be correct, while the locations may have shifted/changed. We formally define a broad class of problems of this type, capturing situations in which the pattern is obtained from the text by a sequence of rearrangements. We consider several natural rearrangement schemes, including the analogues of the ℓ1 and ℓ2 distances, as well as two distances based on interchanges. For these, we present efficient algorithms to solve the resulting string matching problems.

In this paper, we introduce a system, written in Haskell, for filtering information from XML data. Essentially, the system implements a simple declarative language which allows one to extract relevant data as well as to exclude useless and misleading contents from an XML document by matching patterns against XML documents.The matching mechanism employes a cost-based pattern transformation algorithm which searches for patterns in an approximate way (i.e. modulo renaming, insertion, and deletion of XML items) and ranks the results w.r.t. their cost. In order to improve efficiency, the implementation uses sophisticated indexing techniques and exploits laziness to automatically avoid the construction of unnecessary data structures.We analyzed both the expressiveness of our filtering language and the performance of the system using the well known XMark benchmark suite.

We present a fast method for calculation of Hamming distance vector based on a simple preprocessing of the target text. For applications on protein sequences, with alphabet of 20 symbols or more, the proposed method is an order of magnitude faster than the brute force approach while much simpler than previously published methods.

The rapid advance of DNA sequencing technologies has yielded databases of thousands of genomes. To search and index these databases effectively, it is important that we take advantage of the similarity between those genomes. Several authors have recently suggested searching or indexing only one reference genome and the parts of the other genomes where they differ. In this paper we survey the twenty-year history of this idea and discuss its relation to kernelization in parameterized complexity.

Software has become as essential to molecular biologists as the Bunsen burner was a few decades ago. Biological data come mainly in the form of DNA or protein sequences, i.e., strings over alphabets of four or 20 symbols, respectively. The main challenge now is to develop efficient and powerful algorithms to extract as much meaning as possible from the huge amount of data generated in the last few years. In this paper we present a parallel pattern discovery algorithm that given a set of functionally related sequences finds the substrings that occur in all (or most of) the sequences of the set. The occurrences of the substrings can be approximate, that is, can differ up to a maximum number of mismatches that depends on the length of the substrings.

Given a text T over alphabet Σ and a complete index for T constructed using the finite automaton (called the factor automaton or DAWG) accepting all the substrings (factors) of text T. An answer to the query whether a pattern P occurs in text T with k differences is discussed to be done by an algorithm having the time complexity independent on the length of text T. The algorithm searches for the final state of the finite automaton accepting the intersection of languages Fac(T) (the set of all factors of T) and Lk(P) (the set of all strings having at most k differences with respect to pattern P).

We present a novel approach for computing all maximum consecutive subsums in a sequence of positive integers in near-linear time. Solutions for this problem over binary sequences can be used for reporting existence of Parikh vectors in a bit string. Recently, several attempts have been made to build indexes for all Parikh vectors of a binary string in subquadratic time. However, no algorithm is known to date which can beat by more than a polylogarithmic factor the naive @Q(n^2) procedure. We show how to construct a ([email protected])-approximate index for all Parikh vectors of a binary string in O(nlog^2nlog([email protected])) time, for any constant @e>0. Such index is approximate, in the sense that it leaves a small chance for false positives (no false negatives are possible). However, we can tune the parameters of the algorithm so that we can strictly control such a chance of error while still guaranteeing strong subquadratic running time.

International audience; We study strategies of approximate pattern matching that exploit bidirectional text indexes, extending and generalizing ideas of [5]. We introduce a formalism, called search schemes, to specify search strate-gies of this type, then develop a probabilistic measure for the efficiency of a search scheme, prove several combinatorial results on efficient search schemes, and finally, provide experimental computations supporting the superiority of our strategies.

Advances in DNA sequencing mean that databases of thousands of human genomes will soon be commonplace. In this paper, we introduce a simple technique for reducing the size of conventional indexes on such highly repetitive texts. Given upper bounds on pattern lengths and edit distances, we pre-process the text with the lossless data compression algorithm LZ77 to obtain a filtered text, for which we store a conventional index. Later, given a query, we find all matches in the filtered text, then use their positions and the structure of the LZ77 parse to find all matches in the original text. Our experiments show that this also significantly reduces query times.

We present a novel approach for computing all maximum consecutive subsums in a sequence of positive integers in near linear time. Solutions for this problem over binary sequences can be used for reporting existence (and possibly one occurrence) of Parikh vectors in a bit string. Recently, several attempts have been tried to build indexes for all Parikh vectors of a binary string in subquadratic time. However, to the best of our knowledge, no algorithm is know to date which can beat by more than a polylogarithmic factor the natural Θ(n2) exhaustive procedure. Our result implies an approximate construction of an index for all Parikh vectors of a binary string in O(n1+η) time, for any constant η>0. Such index is approximate, in the sense that it leaves a small chance for false positives, i.e., Parikh vectors might be reported which are not actually present in the string. No false negative is possible. However, we can tune the parameters of the algorithm so that we can strictly control such a chance of error while still guaranteeing strong sub-quadratic running time.

Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of Parikh vector q (a “jumbled string”) in the text s requires to find a substring t of s with p(t) = q. The corresponding decision problem is to verify whether at least one such match exists. So, for example for the alphabet Σ = {a, b, c}, the string s = abaccbabaaa has Parikh vector p(s) = (6,3,2), and the Parikh vector q = (2,1,1) appears once in s in position (1,4). Like its more precise counterpart, the renown Exact String Matching, Jumbled Pattern Matching has ubiquitous applications, e.g., string matching with a dyslectic word processor, table rearrangements, anagram checking, Scrabble playing and, allegedly, also analysis of mass spectrometry data. We consider two simple algorithms for Jumbled Pattern Matching and use very complicated data structures and analytic tools to show that they are not worse than the most obvious algorithm. We also show that we can achieve non-trivial efficient average case behavior, but that’s less fun to describe in this abstract so we defer the details to the main part of the article, to be read at the reader’s risk...well, at the reader’s discretion.

Finding approximate overlaps is the first phase of many sequence assembly methods. Given a set of strings of total length n and an error-rate @e, the goal is to find, for all-pairs of strings, their suffix/prefix matches (overlaps) that are within edit distance [email protected][email protected]@[email protected]?, where @? is the length of the overlap. We propose a new solution for this problem based on backward backtracking (Lam, et al., 2008) and suffix filters (Karkkainen and Na, 2008). Our technique uses nH"k+o([email protected])+rlogr bits of space, where H"k is the k-th order entropy and @s the alphabet size. In practice, it is more scalable in terms of space, and comparable in terms of time, than q-gram filters (Rasmussen, et al., 2006). Our method is also easy to parallelize and scales up to millions of DNA reads.

In this paper, we are interested in solving the approximate regular expression matching problem: we are given a regular expression R in advance and we wish to answer the following query: given a text T and a parameter k, find all the substrings of T which match the regular expression R with at most k errors (an error consist in deleting inserting, or substituting a character). There exists a well known solution for this problem in time O(mn) where m is the size of the regular expression (the number of operators and characters appearing in R) and n the length of the text. There also exists a solution for the case k=0 (exact regular expression matching) which solves the problem in time O(dn), where d is the number of strings in the regular expression (a string is a sequence of characters connected with concatenation operator). In this paper, we show that both methods can be combined to solve the approximate regular approximate matching problem in time O(kdn) for arbitrary k. This bound can be much better than the bound O(mn/logk+2n) achieved by the best actual regular expression matching algorithm in case d

We address the problem of searching for a two-dimensional pattern in a two-dimensional text (or image), such that the pattern can be found even if it appears rotated and it is brighter or darker than its occurrence. Furthermore, we consider approximate matching under several tolerance models. We obtain algorithms that are almost optimal both in the worst and the average cases simultaneously. The complexities we obtain are very close to the best current results for the case where only rotations, but not lighting invariance, are supported. These are the first results for this problem under a combinatorial approach.