Asso. Professor, Computer Science, School of Engineering, Amritapuri

Qualification:

Ph.D, MS, BE

bhadrachalam@am.amrita.edu

Phone:

04762802713

Dr. Bhadrachalam Chitturi currently serves as an Associate Professor at the Department of Computer Science and Engineering, Amrita School of Engineering, Amritapuri.

Dr. Bhadrachalam C. was a Research Associate at UTSW Medical Center prior to joining Amrita Vishwa Vidyapeetham. His research interests include Design and Analysis of Algorithms, Bioinformatics, Bio-computation, Computer Networks, and Discrete Mathematics. He has eleven years of professional academic experience. His eight years of professional industrial experience includes Telecommunications, Databases and Image Processing.

**Ph.D. in Computer Science**

University of Texas**M. S. in Computer Science**

University of Texas**B. Tech. in Computer Science & Engineering**

CE Osmania University

Year of Publication | Publication Type | Title |
---|---|---|

2018 |
Journal Article |
Dr. Bhadrachalam Chitturi and Priyanshu Das, “Sorting permutations with transpositions in O(n3) amortized time”, Theoretical Computer Science, 2018.[Abstract] The problem of sorting a permutation π over alphabet ∑={1,2,3…n} with the minimum number of transpositions is known to be intractable. That is, the computation of transposition distance i.e. dt(π), is hard. Such sorting is equivalent to determining the distance between any α, β of the symmetric group Sn over ∑ under the transposition operation. It has applications in computer interconnection networks where a node is denoted by a permutation, and genetics where a genome is modeled by a permutation. The maximum distance between any pair of permutations in Sn is the diameter i.e. diam(Γ(Sn)), of the corresponding Cayley graph Γ(Sn). It corresponds to the maximum latency in the computer interconnection network modeled by Γ(Sn) and the maximum genetic dissimilarity between any pair α, β in Sn. We call transpositions, prefix transpositions, suffix transpositions and prefix/suffix transpositions as block-moves. We design an algorithm to compute dt(π) ∀π in Sn and compute diam(Γ(Sn)) with transpositions in O(n!n3) time and O(n!n2) space; at an amortized time of O(n3). For other block moves, the amortized time for the same is O(n2logn) and total space required is O(n!n). More »» |

2018 |
Journal Article |
Dr. Bhadrachalam Chitturi, Balachander, S., Satheesh, S., and Puthiyoppil, K., “Layered Graphs: Applications and Algorithms”, Algorithms, vol. 11, p. 93, 2018.[Abstract] The computation of distances between strings has applications in molecular biology, music theory and pattern recognition. One such measure, called short reversal distance, has applications in evolutionary distance computation. It has been shown that this problem can be reduced to the computation of a maximum independent set on the corresponding graph that is constructed from the given input strings. The constructed graphs primarily fall into a class that we call layered graphs. In a layered graph, each layer refers to a subgraph containing, at most, some k vertices. The inter-layer edges are restricted to the vertices in adjacent layers. We study the MIS, MVC, MDS, MCV and MCD problems on layered graphs where MIS computes the maximum independent set; MVC computes the minimum vertex cover; MDS computes the minimum dominating set; MCV computes the minimum connected vertex cover; and MCD computes the minimum connected dominating set. The MIS, MVC and MDS are computed in polynomial time if k = Θ(log V). MCV and MCD are computed polynomial time if k = ((log V)α), where α < 1. If k = Θ((log V)1+e), for ∈ > 0, then MIS, MVC and MDS are computed in quasi-polynomial time. If k = Θ(log V), then MCV and MCD are computed in quasi-polynomial time. More »» |

2016 |
Journal Article |
Dr. Bhadrachalam Chitturi and Krishnaveni K. S, “Adjacencies in Permutations”, CoRR, 2016.[Abstract] A permutation on an alphabet Σ, is a sequence where every element in Σ occurs precisely once. Given a permutation π= (π1, π2, π3,....., πn) over the alphabet Σ ={0, 1, . . . , n−1 } the elements in two consecutive positions in π e.g. πi and πi+1 are said to form an \emph{adjacency} if πi+1 =πi+1. The concept of adjacencies is widely used in computation. The set of permutations over Σ forms a symmetric group, that we call Pn. The identity permutation, In ∈ Pn where In =(0,1,2,...,n−1) has exactly n−1 adjacencies. Likewise, the reverse order permutation Rn(∈Pn)=(n−1, n−2, n−3, n−4, ...,0) has no adjacencies. We denote the set of permutations in Pn with exactly k adjacencies with Pn(k). We study variations of adjacency. % A transposition exchanges adjacent sublists; when one of the sublists is restricted to be a prefix (suffix) then one obtains a prefix (suffix) transposition. We call the operations: transpositions, prefix transpositions and suffix transpositions as block-moves. A particular type of adjacency and a particular block-move are closely related. In this article we compute the cardinalities of Pn(k) i.e. ∀k∣Pn (k) ∣ for each type of adjacency in O(n2) time. Given a particular adjacency and the corresponding block-move, we show that ∀k∣Pn(k)∣ and the expected number of moves to sort a permutation in Pn are closely related. Consequently, we propose a model to estimate the expected number of moves to sort a permutation in Pn with a block-move. We show the results for prefix transposition. Due to symmetry, these results are also applicable to suffix transposition. More »» |

2016 |
Journal Article |
Dr. Bhadrachalam Chitturi, Shi, S., Kinch, L. N., and Nick V Grishin, “Compact Structure Patterns in Proteins”, J Mol Biol, vol. 428, no. 21, pp. 4392-4412, 2016.[Abstract] Globular proteins typically fold into tightly packed arrays of regular secondary structures. We developed a model to approximate the compact parallel and antiparallel arrangement of α-helices and β-strands, enumerated all possible topologies formed by up to five secondary structural elements (SSEs), searched for their occurrence in spatial structures of proteins, and documented their frequencies of occurrence in the PDB. The enumeration model grows larger super-secondary structure patterns (SSPs) by combining pairs of smaller patterns, a process that approximates a potential path of protein fold evolution. The most prevalent SSPs are typically present in superfolds such as the Rossmann-like fold, the ferredoxin-like fold, and the Greek key motif, whereas the less frequent SSPs often possess uncommon structure features such as split β-sheets, left-handed connections, and crossing loops. This complete SSP enumeration model, for the first time, allows us to investigate which theoretically possible SSPs are not observed in available protein structures. All SSPs with up to four SSEs occurred in proteins. However, among the SSPs with five SSEs, approximately 20% (218) are absent from existing folds. Of these unobserved SSPs, 80% contain two or more uncommon structure features. More »» |

2015 |
Journal Article |
Dr. Bhadrachalam Chitturi, “Tighter upper bound for sorting permutations with prefix transpositions”, Theoretical Computer Science, vol. 602, pp. 22-31, 2015.[Abstract] Permutations are sequences where each symbol in the given alphabet σ appears exactly once. A transposition is an operation that exchanges two adjacent sublists in a permutation; if one of these sublists is restricted to be a prefix then one obtains a prefix transposition. Transpositions over permutations have applications in genome rearrangements and computer interconnection networks. The set of permutations with n symbols derived from the alphabet σ={0, 1, . . ., n-1} form a symmetric group, that we denote by P<inf>n</inf>. The prefix transposition distance between two permutations π* ∈ P<inf>n</inf> and π ∈P<inf>n</inf> is the minimum number of prefix transpositions, also called moves, needed to transform π* into π . A prefix transposition can be modeled by a permutation operation. A permutation is type of sequence and it is also an operation. The generators for prefix transposition operation are a subset of permutation operation. As a result, transforming an arbitrary π*∈P<inf>n</inf> to an arbitrary π ∈P<inf>n</inf> is equivalent to sorting some π^∈Pn. Thus, upper bound for transforming any π*∈P<inf>n</inf> into any π ∈P<inf>n</inf> with prefix transpositions is simply the upper bound to sort any permutation π∈P<inf>n</inf> with moves. In the article that establishes the best known upper bound for prefix transposition distance over P<inf>n</inf> as n-log<inf>9/2</inf>n, explicit proofs were not given for some cases. In this article, we provide the missing proofs, validating the stated upper bound. Furthermore, we establish an upper bound of n-log<inf>7/2</inf>n for prefix transposition distance over P<inf>n</inf>. © 2015 Published by Elsevier B.V. More »» |

2013 |
Journal Article |
Dr. Bhadrachalam Chitturi, “Erratum:" Upper Bounds for Sorting Permutations with a Transposition Tree"”, Discrete Mathematics, Algorithms and Applications, vol. 5, p. 1392001, 2013. |

2013 |
Journal Article |
Dr. Bhadrachalam Chitturi, “Upper bounds for sorting permutations with a transposition tree”, Discrete Mathematics, Algorithms and Applications, vol. 05, p. 1350003, 2013.[Abstract] An upper bound for sorting permutations with an operation estimates the diameter of the corresponding Cayley graph and an exact upper bound equals the diameter. Computing tight upper bounds for various operations is of theoretical and practical (e.g., interconnection networks, genetics) interest. Akers and Krishnamurthy gave a Ω(n! n2) time method that examines n! permutations to compute an upper bound, f(Γ), to sort any permutation with a given transposition tree T, where Γ is the Cayley graph corresponding to T. We compute two intuitive upper bounds γ and δ′ each in O(n2) time for the same, by working solely with the transposition tree. Recently, Ganesan computed β, an estimate of the exact upper bound for the same, in O(n2) time. Our upper bounds are tighter than f(Γ) and β, on average and in most of the cases. For a class of trees, we prove that the new upper bounds are tighter than β and f(Γ). More »» |

2012 |
Journal Article |
B. - H. Kim, Dr. Bhadrachalam Chitturi, V., N., ,, and , “Self consistency grouping: a stringent clustering method”, Bioinformatics, vol. 13, 2012.[Abstract] Background Methods Results Conclusions |

2012 |
Journal Article |
Dr. Bhadrachalam Chitturi and I Sudborough, H., “Bounding prefix transposition distance for strings and permutations”, Theoretical Computer Science, vol. 421, pp. 15–24, 2012.[Abstract] A transposition is an operation that exchanges two adjacent substrings. Transpositions over permutations, the sequences with no repeated symbols, are related to genome rearrangements. If one of the substrings is restricted to a prefix then it is called a prefix transposition. The prefix transposition distance between a pair of strings (permutations) is the minimum number of prefix transpositions required to transform a given string (permutation) into another given string (permutation). For a permutation of length n, we improve the current prefix transposition distance upper bound of n−log8n to n−log9/2n. For arbitrary strings, we prove new prefix transposition distance upper and lower bounds. For binary strings of length n, we show that n/2 is an upper bound. We show that the prefix transposition distance problem is NP-complete for binary strings. More »» |

2011 |
Journal Article |
Dr. Bhadrachalam Chitturi, “A note on complexity of genetic mutations”, Discrete Mathematics, Algorithms and Applications, vol. 03, pp. 269-286, 2011.[Abstract] Genes, the functional segments of DNA, can be modeled akin to DNA by quaternary strings. Pevzner and Waterman posed various problems pertaining to DNA, e.g. DNA physical mapping, DNA sequencing, and DNA sequence comparison. DNA sequence comparison methods aim to compute the genetic mutation distance. Genetic mutation, a change that happens within a gene, can be modeled by an operation like a transposition or a reversal over a string where a string models a gene. The complexity of transforming quaternary strings under a given operation is equivalent to the complexity of computing the corresponding genetic mutation distance. We show that the string transformation distance under signed prefix reversals, translocations and transreversals is NP-complete. More »» |

2009 |
Journal Article |
S. Shi, Dr. Bhadrachalam Chitturi, and Nick V Grishin, “ProSMoS server: a pattern-based search using interaction matrix representation of protein structures”, Nucleic acids research, vol. 37, pp. W526–W531, 2009.[Abstract] Assessing structural similarity and defining common regions through comparison of protein spatial structures is an important task in functional and evolutionary studies of proteins. There are many servers that compare structures and define sub-structures in common between proteins through superposition and closeness of either coordinates or contacts. However, a natural way to analyze a structure for experts working on structure classification is to look for specific three-dimensional (3D) motifs and patterns instead of finding common features in two proteins. Such motifs can be described by the architecture and topology of major secondary structural elements (SSEs) without consideration of subtle differences in 3D coordinates. Despite the importance of motif-based structure searches, currently there is a shortage of servers to perform this task. Widely known TOPS does not fully address this problem, as it finds only topological match but does not take into account other important spatial properties, such as interactions and chirality. Here, we implemented our approach to protein structure pattern search (ProSMoS) as a web-server. ProSMoS converts 3D structure into an interaction matrix representation including the SSE types, handednesses of connections between SSEs, coordinates of SSE starts and ends, types of interactions between SSEs and beta-sheet definitions. For a user-defined structure pattern, ProSMoS lists all structures from a database that contain this pattern. ProSMoS server will be of interest to structural biologists who would like to analyze very general and distant structural similarities. The ProSMoS web server is available at: http://prodata.swmed.edu/ProSMoS/. More »» |

2009 |
Journal Article |
Dr. Bhadrachalam Chitturi, Fahle, W., Meng, Z., Morales, L., Shields, C. O., Sudborough, I. Hal, and Voit, W., “An (18/11) n upper bound for sorting by prefix reversals”, Theoretical Computer Science, vol. 410, pp. 3372–3390, 2009.[Abstract] The pancake problem asks for the minimum number of prefix reversals sufficient for sorting any permutation of length n. We improve the upper bound for the pancake problem to (18/11)n+O(1)≈(1.6363)n. More »» |

Year of Publication | Publication Type | Title |
---|---|---|

2018 |
Conference Paper |
Dr. Bhadrachalam Chitturi, S. Balachander, S. Satheesh, and K. Puthiyoppil, “MIS, MVC and MDS in Cyclic Layered Graphs”, in IACC 2018., 2018. |

2018 |
Conference Paper |
Dr. Bhadrachalam Chitturi and Srinath T., “Hard Problems on Layered Graphs: Parallel Algorithms and Improvements”, in IACC 2018., 2018. |

2018 |
Conference Paper |
Dr. Bhadrachalam Chitturi and Priyanshu Das, “Scheduling Applications of DAGs”, in Seventh International Conference on Advances in Computing, Communications and Informatics (ICACCI-2018), PES Institute of Technology, Bangalore, 2018., 2018. |

2018 |
Conference Paper |
Athira Selvam, Sravya Kala, and Dr. Bhadrachalam Chitturi, “Counting Chemical Structures Resembling Trees”, in Seventh International Conference on Advances in Computing , Communications and Informatics (ICACCI-2018), PES Institute of Technology, Bangalore, 2018., 2018. |

2018 |
Conference Paper |
G. Rajendran, Dr. Bhadrachalam Chitturi, and Poornachandran, P., “Stance-In-Depth Deep Neural Approach to Stance Classification”, in International Conference on Computational Intelligence and Data Science (ICCIDS 2018)., 2018, vol. 132, pp. 1646-1653.[Abstract] Understanding the user intention from text is a problem of growing interest. The social media like Twitter, Facebook etc. extract user intention to analyze the behaviour of a user which in turn is employed for bot recognition, satire detection, fake news detection etc.. The process of identifying stance of a user from the text is called stance detection. This article compares the headline and body pair of a news article and classifies the pair as related or unrelated. The related pair is further classified into agree, disagree, discuss. We call related as detailed classification and unrelated as broad classification. We employ deep neural nets for feature extraction and stance classification. RNN models and its extensions showed significant variations in the classification of detailed class. Bidirectional LSTM model achieved the best accuracy for broad as well as detailed classification. More »» |

2018 |
Conference Paper |
Dr. Bhadrachalam Chitturi, “Testbed architecture selection and anamoly detection with test flow graphs”, in AFMSS 2018 - 2nd Symposium on Application of Formal Methods for Safety & Security of Critical Systems, 2018. |

2017 |
Conference Paper |
G. Rajendran, Poornachandran, P., and Dr. Bhadrachalam Chitturi, “Deep learning model on stance classification”, in International Conference on Advances in Computing, Communications and Informatics (ICACCI), Udupi, India, 2017.[Abstract] The process of identifying and assigning the relationship between two bodies of text is referred to as stance classification. Given a headline and the corresponding body they are compared and their relationship is classified into one of the following two classes - unrelated or related where related is further divided into agree, disagree and discuss. In this article, data is collected from news articles which contains headlines and bodies. We call a headline and the corresponding body as a pair. Deep learning models are applied to these pairs. We applied bidirectional Long Short-Term Memory (LSTM) model and multi-layered perceptron (MLP) model and obtained accuracies of 83.5% and 78% respectively. The accuracy calculation is based on a weighted scheme. The correctly classified unrelated pair has a score of 0.25. A pair correctly classified as related yields a score of one only if the the sub-relationships of agree, disagree and discuss are correctly identified; otherwise, the score is 0.25. More »» |

2017 |
Conference Paper |
S. Uthan and Dr. Bhadrachalam Chitturi, “Bounding the diameter of cayley graphs generated by specific transposition trees”, in 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Udupi, India, 2017.[Abstract] A transposition tree T can be defined over permutations where the positions within a permutation define the vertices of the tree and an edge (i, j) of T signifies that the symbols at the positions i and j can be swapped. A Cayley graph of a permutation group can be generated by a transposition tree T where the edges of T form the generator set. Identifying the diameter value of a Cayley graph helps is equivalent to determining the maximum possible latency of communication in the corresponding interconnection network where the latency is measured in terms of the number of hops. In general, computation of the diameter is intractable. Thus, determining an upper bound on the diameter value is sought. In particular, tighter upper bounds are keenly pursued. Several existing methods compute an upper bound on the diameter value. The first known method has exponential time complexity. Later on, several articles introduced polynomial time algorithms. This article compares various methods. Furthermore, exact diameters for novel classes of trees are identified. More »» |

2016 |
Conference Paper |
K. P. Sinsha and Dr. Bhadrachalam Chitturi, “A study of gene prioritization algorithms on PPI networks”, in 2016 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2016.[Abstract] The undiscovered genes that contribute to a particular disease are of great interest in medical informatics. The candidate pool of such genes from GWAS or similar studies is typically vast. A direct experimental verification all such genes is prohibitively expensive in terms of time and money. In order to limit the number of candidates for experimental verification, numerous computational methods have been developed. One of the most widely used technique applies gene prioritization(GP) algorithms on a weighted protein-protein interaction network (PPIN). We analyzed the popular GP algorithms in semiautomatic manner. The idea is to study their behavior, rank them and attempt to improve their performance by modifying them. Additionally, we derived an expression for the steady state scores of the power method. More »» |

2015 |
Conference Paper |
Dr. Bhadrachalam Chitturi, Thomas, J., and Indulekha T.S., “New approaches for discovering unsupervised human activities by mining sensor data”, in 2015 International Conference on Computing and Network Communications, CoCoNet 2015, 2015, pp. 118-123.[Abstract] Discovering human activities facilitates computerization and the consequent monitoring of the smart home environment. The existing unsupervised human activity discovery systems perform segmentation clustering followed by the labeling of the sensor data. Segmentation clustering consists of forming segments from similar consecutive frames and then clustering similar segments. A cluster is labeled by the action associated with its most frequent sensor(s). In these methods, even if similar segments denote distinct activities they often occur in the same cluster. We propose three alternate methods to address this issue. The first method is a minor variant of the segmentation clustering where subsequences of the segments are clustered instead of the segments. We employ the concept of cover where (a, b, c) subsumes (a, c) if they have identical frequency. The second method employs a new algorithm, i.e. LRS, instead of segmentation. The third method is a hybrid method that extracts subsequences from the output of LRS. We compared the proposed systems with the existing system on CASAS dataset, a real world human activity dataset. The third method that employs LRS followed by subsequence extraction yielded the best Dunn's index and the best correctness in clusters as per confusion matrix. © 2015 IEEE. More »» |

2012 |
Conference Paper |
P. Achan, Warrier, A. G., and Dr. Bhadrachalam Chitturi, “Biological Data Handling Methods”, presented at the 04/2012, 2012.[Abstract] Biological data has more variation in type and format compared to other types of data. Thus, it poses new challenges. However, it encapsulates critical information; thus, handling it is of primary interest. Data handling includes storage and retrieval of data with associated formats and methods of data transfer, data format conversion, algorithms that run on the data and the output methods including visualization of the results. High throughput methods have been yielding biological data at a fast pace. This data includes protein-protein interactions, gene sequences, gene co-expressions, and protein sequences. This data is supplemented with huge amounts of clinical data conveniently captured in electronic medical records and the wet lab data. We describe the current approaches, each with a model system and identify its key contributions. We propose some ideas for biological data handling in the future. More »» |

2012 |
Conference Paper |
B. Xie, Sulakhe, D., Dr. Bhadrachalam Chitturi, Agam, G., Maltsev, N., and Gilliam, T. C., “Prediction of candidate genes for neuropsychiatric disorders using feature-based enrichment”, in 2012 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2012, Orlando, FL, 2012, pp. 564-566.[Abstract] The progress in understanding of molecular mechanisms underlying common heritable disorders (e.g. autism, schizophrenia, diabetes) depends on the availability of new bioinformatics approaches for identification of their characteristic genetic variations and associated multidimensional patterns of inheritance. High-throughput genome-wide studies (e.g. sequencing, gene expression profiling) result in hundreds of potential candidate genes. Prioritizing these genes and finding the best candidates contributing to a disease phenotype is one of the most important problems of genomics. We present an approach for prioritization of disease candidate genes using Support Vector Machine (SVM) and ontology associations. Features are extracted from both hierarchical and non-hierarchical ontology space (e.g user defined customized ontologies, Gene Ontology(GO) ). We select a subset of features according to enrichment scores in a training set of genes and use these to train a classifier using SVM. Ranking of the genes in the query set (e.g. the results of gene expression analysis) is based on a distance from the decision boundary to data points. Results obtained using the proposed approach to the analysis of several neurological disorders (autism, mental retardation, and agenesis of corpus callosum) are presented. More »» |

2010 |
Conference Paper |
Dr. Bhadrachalam Chitturi, Bein, D., and Grishin, N. V., “Complete enumeration of compact structural motifs in proteins”, in Proceedings of the International Symposium on Biocomputing, 2010.[Abstract] The search of structural motifs that specify the spatial arrangement of polypeptide segments is preferred over other methods such as common substructure discovery and structural superposition in comparing protein structures. 3D protein structures can be modeled as graphs whose maximum degree is bounded by a constant. Structural motifs can also be modeled as graphs and a significant percentage of them are trees. Thus, motif search in proteins can be modeled as an enumeration of isomorphic subgraphs where a query tree Q with m nodes is searched in a sparse graph G with n nodes and the maximum degree of any node in G is bounded by a constant ε. We design an efficient divide-and-conquer algorithm that finds all copies of Q in G by partitioning Q using a minimum dominating set. This strategy can be extended to sparse query graphs that can be reduced to trees by deleting a small number of edges. More »» |

2010 |
Conference Paper |
Dr. Bhadrachalam Chitturi, “On complexity of transforming strings”, in Proceedings of 11th International Conference in Bioinformatics and Computational Biology, BIOCOMP 2010, 2010.[Abstract] Genes can be modeled by strings defined over a finite alphabet. Pevzner and Waterman posed various problems pertaining to DNA (a string with an alphabet of size four), i.e. DNA physical mapping, DNA sequencing, and DNA sequence comparison (mimicking genetic mutations). Genetic mutations, the changes that happen within a gene, can be modeled by operations like transpositions and reversals over strings. The complexity of transforming strings under such operations is of primary interest. We show that the string transformation distance under cut-and-paste moves, prefix reversal/transpositions, and translocations is NP-complete. More »» |

2010 |
Conference Paper |
Dr. Bhadrachalam Chitturi and Sudborough, I. Hal, “Prefix Reversals on Strings”, in International Conference on Bioinformatics & Computational Biology, BIOCOMP 2010, 2010.[Abstract] A reversal is an operation that reverses a substring. When the chosen substring is restricted to a prefix it is called a prefix reversal. Given two strings, α and β, the problem of finding the minimum number of prefix reversals that transform α into β is called the prefix reversal distance problem. This problem is a version of the reversal distance problem, related to genetic rearrangements. An upper bound of 18n/11 and a lower bound of 15n/14 are known for permutations. We give bounds for prefix reversals on strings. For example, n-1 prefix reversals are sufficient to transform a given n-binary string into a compatible string, i.e. a string with same frequency for each symbol as the given string. We also prove that the prefix reversal distance for strings is NP-complete. More »» |

2008 |
Conference Paper |
Dr. Bhadrachalam Chitturi and Sudborough, I. H., “Bounding Prefix Transposition Distance for Strings and Permutations”, in Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008), 2008.[Abstract] A transposition is an operation that exchanges two adjacent substrings. When it is restricted so that one of the substrings is a prefix, it is called a prefix transposition. The prefix transposition distance between a pair of strings (permutations) is the shortest sequence of prefix transpositions required to transform a given string (permutation) into another given string (permutation). This problem is a variation of the transposition distance problem, related to genome rearrangements. An upper bound of n-1 and a lower bound of n/2 are known. We improve the bounds to n-log8 n and 2n/3 respectively. We also give upper and lower bounds for the prefix transposition distance on strings. For example, n/2 prefix transpositions are always sufficient for binary strings. We also prove that the exact prefix transposition distance problem on strings is NP complete. More »» |

Year of Publication | Publication Type | Title |
---|---|---|

2014 |
Book Chapter |
D. Sulakhe, Balasubramanian, S., Xie, B., Berrocal, E., Feng, B., Taylor, A., Dr. Bhadrachalam Chitturi, Dave, U., Agam, G., Xu, J., Börnigen, D., Dubchak, I., T. Gilliam, C., and Maltsev, N., “High-Throughput Translational Medicine: Challenges and Solutions”, in Systems Analysis of Human Multigene Disorders, N. Maltsev, Rzhetsky, A., and T. Gilliam, C. New York, NY: Springer New York, 2014, pp. 39–67.[Abstract] Recent technological advances in genomics now allow producing biological data at unprecedented tera- and petabyte scales. Yet, the extraction of useful knowledge from this voluminous data presents a significant challenge to a scientific community. Efficient mining of vast and complex data sets for the needs of biomedical research critically depends on seamless integration of clinical, genomic, and experimental information with prior knowledge about genotype–phenotype relationships accumulated in a plethora of publicly available databases. Furthermore, such experimental data should be accessible to a variety of algorithms and analytical pipelines that drive computational analysis and data mining. Translational projects require sophisticated approaches that coordinate and perform various analytical steps involved in the extraction of useful knowledge from accumulated clinical and experimental data in an orderly semiautomated manner. It presents a number of challenges such as (1) high-throughput data management involving data transfer, data storage, and access control; (2) scalable computational infrastructure; and (3) analysis of large-scale multidimensional data for the extraction of actionable knowledge. More »» |

2012 |
Book Chapter |
Natarajan Meghanathan and Dr. Bhadrachalam Chitturi, “A secure session transfer protocol for downloading a large file across a cluster of servers in the presence of network congestion”, in Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST, vol. 84, Bangalore: , 2012, pp. 552-562.[Abstract] We propose the design of a Session Transfer Protocol (STP) that allows a client to download a large file replicated across several servers. STP runs at the session layer, on the top of the standard Transmission Control Protocol (TCP). A client can sequentially download the entire file from one or more servers, from one server at a time, with just one TCP session. A STP Server, currently sending the contents of a file to a client, can proactively detect congestion in the network and transfer a file download session to another peer STP Server that is located in a different network. At any stage (initial session establishment or session transfer), the STP Client chooses a particular server by executing certain selection tests among the servers in the list sent by the STP Gateway, which is the public face of the cluster of STP Servers in the Internet. Unlike the traditional File Transfer Protocol (FTP) that requires users to repeatedly initiate the entire download process upon the failure of each FTP connection, STP is seamless, incremental and provides improved Quality of Service while downloading a large file. The user working at the STP Client is unaware of the congestion and resulting session transfer to a different STP Server. STP is security-aware and has appropriate encryption, authentication and anti-spoofing features incorporated at different stages of its execution. © Institute for Computer Sciences, Social Informatics and Telecommunications Engineering 2012. More »» |

2010 |
Book Chapter |
X. Feng, Dr. Bhadrachalam Chitturi, and Sudborough, H., “Sorting Circular Permutations by Bounded Transpositions”, in Advances in Computational Biology, H. R. Arabnia New York, NY: Springer New York, 2010, pp. 725–736.[Abstract] A k-bounded (k ≥ 2) transposition is an operation that switches two elements that have at most k − 2 elements in between. We study the problem of sorting a circular permutation $π$ of length n for k = 2, i.e., adjacent swaps and k = 3, i.e., short swaps. These transpositions mimic microrearrangements of gene order in viruses and bacteria. We prove a (1/4)n 2 lower bound for sorting by adjacent swaps. We show upper bounds of (5/32)n 2 + O(n log n) and (7/8)n + O(log n) for sequential and parallel sorting, respectively, by short swaps. More »» |

2008 |
Book Chapter |
Dr. Bhadrachalam Chitturi, Sudborough, H., Voit, W., and Feng, X., “Adjacent Swaps on Strings”, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5092, X. Hu and Wang, J. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 299–308.[Abstract] Transforming strings by exchanging elements at bounded distance is applicable in fields like molecular biology, pattern recognition and music theory. A reversal of length two at position i is denoted by (i i+1). When it is applied to π, where π = π 1,π 2, π 3,..., π i ,π i∈+∈1, π n , it transforms π to π′, where π′ = π 1,π 2, π 3,..., π i∈-∈1,π i∈+∈1, π i , π i∈+∈1, ..., π n . We call this operation an adjacent swap. We study the problem of computing the minimum number of adjacent swaps needed to transform one string of size n into another compatible string over an alphabet σ of size k, i.e. adjacent swap distance problem. O(nlog 2 n) time complexity algorithms are known for adjacent swap distance. We give an algorithm with O(nk) time for both signed and unsigned versions of this problem where k is the number of symbols. We also give an algorithm with O(nk) time for transforming signed strings with reversals of length up to 2, i.e. reversals of length 1 or 2. © 2008 Springer-Verlag Berlin Heidelberg. More »» |

Year of Publication | Publication Type | Title |
---|---|---|

2007 |
Thesis |
Dr. Bhadrachalam Chitturi and Sudborough, I. Hal, “On transforming sequences”, University of Texas at Dallas, 2007.[Abstract] Sequences are well defined mathematical objects which include strings, permutations, and vectors. In this thesis, a “sequence” refers to an object which is either a string over a finite alphabet or a permutation. The measure of similarity among sequences is of fundamental importance. Given an operation, distance is a metric that measures similarity. That is, the fewer the number of operations required to transform one sequence to another, the greater the similarity. Specifically, it is shown for prefix transpositions on strings that one can transform a string into a compatible string in at most n−α moves, where α is the frequency of occurrence of the most frequent symbol and the problem of finding the exact prefix transposition distance is NP-complete. For prefix transpositions on permutations of length n, it is shown that 2 n/3 is a lower bound and n−log8( n) is an upper bound. A proof of NP-completeness is shown for prefix reversal distance on strings, cut-and-paste move distance on strings, and simultaneous prefix reversal and prefix transposition distance on strings. In addition, it is shown that one can compute the number of reversals of length 2 to transform a given string S into a compatible string T over a k symbol alphabet in O( n·k) time. More »» |

- B. Chitturi, Krishnaveni K S. "Adjacencies in Permutations." arXiv preprint arXiv:1601.04469 (2016). We detected some minor errors in the computation of the probabilities. Certain assumptions must have been more explicit.
- B. Chitturi, IH Sudborough: Bounding prefix transposition distance for strings and permutations. Theor. Comput. Sci. 421: 15-24 (2012)

In page 4: (3) for all i, the symbol t_{i-1}is in a position to the right of s_{i+1}. t_{i-1}should be read as t_{i}-1. This is explained in the text that follows this condition.

[11]B. Chitturi, I.H. Sudborough, On complexity of transforming strings, in: Proceedings of International Conference in Bioinformatics and Computational Biology, BIOCOMP 2010, pp. 591-598.

Must be:

[11]B. Chitturi, On complexity of transforming strings, in: Proceedings of International Conference in Bioinformatics and Computational Biology, BIOCOMP 2010, pp. 584-590. - B. Chitturi, D. Bein, NV Grishin. Complete enumeration of compact structural motifs in proteins. In Proceedings of the International Symposium on Biocomputing 2010 Feb 15 (p. 19). ACM.

Dom_Set algorithm was meant to be the standard dynamic programming algorithm that was known. However, the algorithm stated in the paper is incorrect. At the time of the publication, regretfully, the authors were unfamiliar with the associated reference (given below). In later articles the reference was cited.

EJ Cockayne, S Goodman, S Hedetniemi. A linear algorithm for the domination number of a tree. Information Processing Letters, 4(2):41-4, 1Nov 1 975. - B. Chitturi, I.H. Sudborough, Prefix reversals on strings, in: Proceedings of International Conference in Bioinformatics and Computational Biology, BIOCOMP 2010, pp. 591-598. PTAS must be simply read as an approximation algorithm.

Faculty Research Interest: