Search

Graphs are arguably one of the most fundamental data-structure used in many domains such as block-chain, networks etc. Theoretically and practically, improving Graph performance is one of the most studied and omnipresent research problems. In this paper, we have implemented a dynamic unbounded concurrent graph which can perform the add, delete or lookup operations on vertices and edges concurrently. All these methods are lock-free and linearizable. On top of this, we have also implemented the wait-free graph snapshot algorithm. To the best of knowledge this is first wait-free implementation of snapshot on concurrent graphs. We have used the snapshot of the algorithm to calculate the diameter and between centrality. We have compared our implementation with its counterparts and outperformed them by a good margin. This illustrates the efficiency of our snapshot method which is a generic method and can be used to perform other useful graph analytics operations.

Non-blocking search data structures offer scalability with a progress guarantee on high-performance multi-core architectures. In the recent past, "learned queries" have gained remarkable attention. It refers to predicting the rank of a key computed by machine learning models trained to infer the cumulative distribution function of an ordered dataset. A line of works exhibits the superiority of learned queries over classical query algorithms. Yet, to our knowledge, no existing non-blocking search data structure employs them. In this paper, we introduce \textbf{Kanva}, a framework for learned non-blocking search. Kanva has an intuitive yet non-trivial design: traverse down a shallow hierarchy of lightweight linear models to reach the "non-blocking bins," which are dynamic ordered search structures. The proposed approach significantly outperforms the current state-of-the-art -- non-blocking interpolation search trees and elimination (a,b) trees -- in many workload and data distributions. Kanva is provably linearizable.

CRUD operations, along with range queries make a highly useful abstract data type (ADT), employed by many dynamic analytics tasks. Despite its wide applications, to our knowledge, no fully wait-free data structure is known to support this ADT. In this paper, we introduce Uruv, a proactive linearizable and practical wait-free concurrent data structure that implements the ADT mentioned above. Structurally, Uruv installs a balanced search index on the nodes of a linked list. Uruv is the first wait-free and proactive solution for concurrent B+tree. Experiments show that Uruv significantly outperforms previously proposed lock-free B+trees for dictionary operations and a recently proposed lock-free method to implement the ADT mentioned above.

Biped robots have plenty of benefits over wheeled, quadruped, or hexapod robots due to their ability to behave like human beings in tough and non-flat environments. Deformable terrain is another challenge for biped robots as it has to deal with sinkage and maintain stability without falling. In this study, we are proposing a Deep Deterministic Policy Gradient (DDPG) approach for motion control of a flat-foot biped robot walking on deformable terrain. We have considered a 7-link biped robot for our proposed approach. For soft soil terrain modeling, we have considered triangular Mesh to describe its geometry, where mesh parameters determine the softness of soil. All simulations have been performed on PyChrono, which can handle soft soil environments., Comment: Advances in Robotics (AIR) 2023 IIT Ropar

A novel efficient downstairs trajectory is proposed for a 9 link biped robot model with toe-foot. Brachistochrone is the fastest descent trajectory for a particle moving only under the influence of gravity. In most situations, while climbing downstairs, human hip also follow brachistochrone trajectory for a more responsive motion. Here, an adaptive trajectory planning algorithm is developed so that biped robots of varying link lengths, masses can climb down on varying staircase dimensions. We assume that the center of gravity (COG) of the biped concerned lies on the hip. Zero Moment Point (ZMP) based COG trajectory is considered and its stability is ensured. Cycloidal trajectory is considered for ankle of the swing leg. Parameters of both cycloid and brachistochrone depends on dimensions of staircase steps. Hence this paper can be broadly divided into 4 steps 1) Developing ZMP based brachistochrone trajectory for hip 2) Cycloidal trajectory planning for ankle by taking proper collision constraints 3) Solving Inverse kinematics using unsupervised artificial neural network (ANN) 4) Comparison between the proposed, a circular arc and a virtual slope based hip trajectory. The proposed algorithms have been implemented using MATLAB., Comment: 6 pages, 6 figures, Accepted for presentation at the RoAI 2020: International Conference on Robotics and Artificial Intelligence 2020, IIT Madras and will be published in the Proceedings by the Journal of Physics: Conference Series. arXiv admin note: substantial text overlap with arXiv:2012.01417

In this paper, a novel optimal technique for joint angles trajectory tracking control with energy optimization for a biped robot with toe foot is proposed. For the task of climbing stairs by a 9-link biped model, a cycloid trajectory for swing phase is proposed in such a way that the cycloid variables depend on the staircase dimensions. Zero Moment Point(ZMP) criteria is taken for satisfying stability constraint. This paper mainly can be divided into 3 steps: 1) Planning stable cycloid trajectory for initial step and subsequent step for climbing upstairs and Inverse Kinematics using an unsupervised artificial neural network with knot shifting procedure for jerk minimization. 2) Modeling Dynamics for Toe foot biped model using Lagrange Dynamics along with contact modeling using spring-damper system followed by developing Neural Network Temporal Quantized Lagrange Dynamics which takes inverse kinematics output from neural network as its inputs. 3) Using Ant Colony Optimization to tune PD (Proportional Derivative) controller parameters and torso angle with the objective to minimize joint space trajectory errors and total energy consumed. Three cases with variable staircase dimensions have been taken and a brief comparison is done to verify the effectiveness of our proposed work Generated patterns have been simulated in MATLAB .

The recA/RAD51 gene family encodes a diverse set of recombinase proteins that effect homologous recombination, DNA-repair, and genome stability. The recA gene family is expressed in almost all species of Eubacteria, Archaea, and Eukaryotes, and even in some viruses. To date, efforts to resolve the deep evolutionary origins of this ancient protein family have been hindered, in part, by the high sequence divergence between families (i.e. ~30% identity between paralogous groups). Through (i) large taxon sampling, (ii) the use of a phylogenetic algorithm designed for measuring highly divergent paralogs, and (iii) novel Evolutionary Spatial Dynamics simulation and analytical tools, we obtained a robust, parsimonious and more refined phylogenetic history of the recA/RAD51 superfamily. Taken together, our model for the evolution of recA/RAD51 family provides a better understanding of ancient origin of recA proteins and multiple events leading to the diversification of recA homologs in eukaryotes, including the discovery of additional RAD51 sub-families., Comment: 21 pages, 11 figures, 1 table

Accurately assigning folds for divergent protein sequences is a major obstacle to structural studies and underlies the inverse protein folding problem. Herein, we outline our theories for fold-recognition in the "twilight-zone" of sequence similarity (<25% identity). Our analyses demonstrate that structural sequence profiles built using Position-Specific Scoring Matrices (PSSMs) significantly outperform multiple popular homology-modeling algorithms for relating and predicting structures given only their amino acid sequences. Importantly, structural sequence profiles reconstitute SCOP fold classifications in control and test datasets. Results from our experiments suggest that structural sequence profiles can be used to rapidly annotate protein folds at proteomic scales. We propose that encoding the entire Protein DataBank (~1070 folds) into structural sequence profiles would extract interoperable information capable of improving most if not all methods of structural modeling., Comment: 22 pages, 11 figures

The inability to resolve deep node relationships of highly divergent/rapidly evolving protein families is a major factor that stymies evolutionary studies. In this manuscript, we propose a Multiple Sequence Alignment (MSA) independent method to infer evolutionary relationships. We previously demonstrated that phylogenetic profiles built using position specific scoring matrices (PSSMs) are capable of constructing informative evolutionary histories(1;2). In this manuscript, we theorize that PSSMs derived specifically from the query sequences used to construct the phylogenetic tree will improve this method for the study of rapidly evolving proteins. To test this theory, we performed phylogenetic analyses of a benchmark protein superfamily (reverse transcriptases (RT)) as well as simulated datasets. When we compare the results obtained from our method, PHYlogenetic ReconstructioN (PHYRN), with other MSA dependent methods, we observe that PHYRN provides a 4- to 100-fold increase in accurate measurements at deep nodes. As phylogenetic profiles are used as the information source, rather than MSA, we propose PHYRN as a paradigm shift in studying evolution when MSA approaches fail. Perhaps most importantly, due to the improvements in our computational approach and the availability of vast amount of sequencing data, PHYRN is scalable to thousands of sequences. Taken together with PHYRNs adaptability to any protein family, this method can serve as a tool for resolving ambiguities in evolutionary studies of rapidly evolving/highly divergent protein families., Comment: 13 pages, 6 figures

In this study, we explored the utility of a descriptive and predictive bionetwork model for phospholipase C-coupled calcium signaling pathways, built with non-kinetic experimental information. Boolean models generated from these data yield oscillatory activity patterns for both the endoplasmic reticulum resident inositol-1,4,5-trisphosphate receptor (IP3R) and the plasma-membrane resident canonical transient receptor potential channel 3 (TRPC3). These results are specific as randomization of the Boolean operators ablates oscillatory pattern formation. Furthermore, knock-out simulations of the IP3R, TRPC3, and multiple other proteins recapitulate experimentally derived results. The potential of this approach can be observed by its ability to predict previously undescribed cellular phenotypes using in vitro experimental data. Indeed our cellular analysis of the developmental and calcium-regulatory protein, DANGER1a, confirms the counter-intuitive predictions from our Boolean models in two highly relevant cellular models. Based on these results, we theorize that with sufficient legacy knowledge and/or computational biology predictions, Boolean networks provide a robust method for predictive-modeling of any biological system., Comment: 19 pages, 5 Figures, 2 Tables

Just as physicists strive to develop a TOE (theory of everything), which explains and unifies the physical laws of the universe, the life-scientist wishes to uncover the TOE as it relates to cellular systems. This can only be achieved with a quantitative platform that can comprehensively deduce and relate protein structure, functional, and evolution of genomes and proteomes in a comparative fashion. Were this perfected, proper analyses would start to uncover the underlying physical laws governing the emergent behavior of biological systems and the evolutionary pressures responsible for functional innovation. In the near term, such methodology would allow the vast quantities of uncharacterized (e.g. metagenomic samples) primary amino acid sequences to be rapidly decoded. Analogous to natural products found in the Amazon, genomes of living organisms contain large numbers of proteins that would prove useful as new therapeutics for human health, energy sources, and/or waste management solutions if they could be identified and characterized. We previously theorized that phylogenetic profiles could provide a quantitative platform for obtaining unified measures of structure, function, and evolution (SF&E)(1). In the present manuscript, we present data that support this theory and demonstrates how refinements of our analysis algorithms improve the performance of phylogenetic profiles for deriving structural/functional relationships., Comment: 18 pages, 8 figures