Identity-based encryption with wildcards in the standard model

In this article, based on Chatterjee-Sarkar＇ hierarchical identity-based encryption （HIBE）, a novel identity-based encryption with wildcards （WIBE） scheme is proposed and is proven secure in the standard model （without random oracle）. The proposed scheme is proven to be secure assuming that the decisional Bilinear Diffie-Hellman （DBDH） problem is hard. Compared with the Wa-WIBE scheme that is secure in the standard model, our scheme has shorter common parameters and ciphertext length.

Pattern Matching with Flexible Wildcards

Pattern matching with wildcards（PMW） has great theoretical and practical significance in bioinformatics,information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only is the number of all matches exponential with respect to the maximal gap flexibility and the pattern length, but the matching positions in PMW are also hard to choose. The objective to count the maximal number of matches one by one is computationally infeasible. Therefore,rather than solving the generic PMW problem, many research efforts have further defined new problems within PMW according to different application backgrounds. To break through the limitations of either fixing the number or allowing an unbounded number of wildcards, pattern matching with flexible wildcards（PMFW） allows the users to control the ranges of wildcards. In this paper, we provide a survey on the state-of-the-art algorithms for PMFW, with detailed analyses and comparisons, and discuss challenges and opportunities in PMFW research and applications.

Multi-Pattern Matching Algorithm with Wildcards Based on Bit-Parallelism

Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set {p^1,… ,p^k} in a given text t. If the percentage of wildcards in pattern set is not high, this problem can be solved using finite automata. We introduce a multi-pattern matching algorithm with a fixed number of wildcards to overcome the high percentage of the occurrence of wildcards in patterns. In our proposed method, patterns are matched as bit patterns using a sliding window approach. The window is a bit window that slides along the given text, matching against stored bit patterns. Matching process is executed using bit wise operations. The experimental results demonstrate that the percentage of wildcard occurrence does not affect the proposed algorithm＇s performance and the proposed algorithm is more efficient than the algorithms based on the fast Fourier transform. The proposed algorithm is simple to implement and runs efficiently in O（n ＋ d（n/σ ）（m/w）） time, where n is text length, d is symbol distribution over k patterns, m is pattern length, and σ is alphabet size.

Estimating ancestral distributions of lineages with uncertain sister groups:a statistical approach to Dispersal-Vicariance Analysis and a case using Aesculus L.(Sapindaceae) including fossils

We propose a simple statistical approach for using Dispersal-Vicariance Analysis （DIVA） software to infer biogeographic histories without fully bifurcating trees. In this approach, ancestral ranges are first optimized for a sample of Bayesian trees. The probability P of an ancestral range r at a node is then calculated as P（rY） = ∑t^n=1 F（rY）t Pt where Y is a node, and F（rY） is the frequency of range r among all the optimal solutions resulting from DIVA optimization at node Y, t is one of n topologies optimized, and Pt is the probability of topology t. Node Y is a hypothesized ancestor shared by a specific crown lineage and the sister of that lineage ＂x＂, where x may vary due to phylogenetic uncertainty （polytomies and nodes with posterior probability 〈 100%）. Using this method, the ancestral distribution at Y can be estimated to provide inference of the geographic origins of the specific crown group of interest. This approach takes into account phylogenetic uncertainty as well as uncertainty from DIVA optimization. It is an extension of the previously described method called Bayes-DIVA, which pairs Bayesian phylogenetic analysis with biogeographic analysis using DIVA. Further, we show that the probability P of an ancestral range at Y calculated using this method does not equate to pp＊F（rY） on the Bayesian consensus tree when both variables are 〈 100%, where pp is the posterior probability and F（rY） is the frequency of range r for the node containing the specific crown group. We tested our DIVA-Bayes approach using Aesculus L., which has major lineages unresolved as a polytomy. We inferred the most probable geographic origins of the five traditional sections of Aesculus and ofAesculus californica Nutt. and examined range subdivisions at parental nodes of these lineages. Additionally, we used the DIVA-Bayes data from Aesculus to quantify the effects on biogeographic inference of including two wildcard fossil taxa in phylogenetic analysis. Our analysis resolved the geographic ranges of the parental nodes of the lineages of Aesculus with moderate to high probabilities. The probabilities were greater than those estimated using the simple calculation ofpp＊F（rY） at a statistically significant level for two of the six lineages. We also found that adding fossil wildcard taxa in phylogenetic analysis generally increased P for ancestral ranges including the fossil＇s distribution area. The AP was more dramatic for ranges that include the area of a wildcard fossil with a distribution area underrepresented among extant taxa. This indicates the importance of including fossils in biogeographic analysis. Exmination of range subdivision at the parental nodes revealed potential range evolution （extinction and dispersal events） along the stems ofA. californica and sect. Parryana.