Qualification: 
Ph.D
Email: 
bhadrachalam@am.amrita.edu
Phone: 
04762802713

Dr. Bhadrachalam Chitturi currently serves as the 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.

Education

  • 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

Publications

Publication Type: Journal Article

Year of Publication Publication Type Title

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 »»

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 »»

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, “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 »»

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.

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 »»

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
Numerous types of clustering like single linkage and K-means have been widely studied and applied to a variety of scientific problems. However, the existing methods are not readily applicable for the problems that demand high stringency.

Methods
Our method, self consistency grouping, i.e. SCG, yields clusters whose members are closer in rank to each other than to any member outside the cluster. We do not define a distance metric; we use the best known distance metric and presume that it measures the correct distance. SCG does not impose any restriction on the size or the number of the clusters that it finds. The boundaries of clusters are determined by the inconsistencies in the ranks. In addition to the direct implementation that finds the complete structure of the (sub)clusters we implemented two faster versions. The fastest version is guaranteed to find only the clusters that are not subclusters of any other clusters and the other version yields the same output as the direct implementation but does so more efficiently.

Results
Our tests have demonstrated that SCG yields very few false positives. This was accomplished by introducing errors in the distance measurement. Clustering of protein domain representatives by structural similarity showed that SCG could recover homologous groups with high precision.

Conclusions
SCG has potential for finding biological relationships under stringent conditions.

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

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 »»

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 »»

Publication Type: Conference Paper

Year of Publication Publication Type Title

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

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 »»

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 »»

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 »»

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, 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 »»

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 »»

Publication Type: Book Chapter

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 »»

Publication Type: Thesis

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.
Several types of operations and their associated distances have been studied on permutations and strings. This thesis studies: (a) prefix transpositions and prefix reversals, as well as reversals of length 2 and the associated distance calculations on strings, (b) the prefix transposition operation on permutations and (c) the computational complexity of corresponding problems. For the operations mentioned above, upper and lower bounds, complexity results, and approximation strategies are given.

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 »»

ERRATA

  • B. Chitturi. Layered graphs: a class that admits polynomial time solutions for some hard problems. [link]
    The writing is not finalized yet.
    The heading for Compatibility is at the wrong place, an additional paragraph is incorrectly included.
    The compatibility conditions for CVC and CDC are not completely specified. In the end they must form a single component. To this end, we must carry forward the connected components in the current mask. Consider CVC; clearly each layer must choose a mask that is a VC. (a) The previous layer mask l corresponds to one component.
    (b) The previous layer mask l corresponds to more than one component.
    Case(a): Infeasible mask for this layer i, j: No vertex from j connects with $l$ or all the inter-layer edges between layers i-1 and i are not covered.
    If at least one edge exists across j and l: (i) j is a single connected component then the result is also a single component (consisting of all chosen cvertices).
    (ii) j has more than one connected component and all of them connect to l then the result is also a single component.
    (ii) j has more than one connected component and only some of them connect to l then the result consists of many components. All components from j connected to l become one component all the rest are separate components.
    (iii) Thus, for a j we store all paritions of vertices where when j is chosen and the current components are denoted by the sets in a partition the sub-solution with minimum cardinality is chosen.
    (iv) Thus, for each mask j we have at most Bell Number( cardinality(j)) solutions are stored. cardinality(j) is the number of bits that are set in j.
    When the mask $x$ is chosen for the last layer then the vertices of the mask must be connected to the components of the previous layer and yield a single component.
  • 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 ti-1 is in a position to the right of si+1 . ti-1 should be read as ti-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.
     
207
PROGRAMS
OFFERED
5
AMRITA
CAMPUSES
15
CONSTITUENT
SCHOOLS
A
GRADE BY
NAAC, MHRD
9th
RANK(INDIA):
NIRF 2017
150+
INTERNATIONAL
PARTNERS
  • Amrita on Social Media

  • Contact us

    Amrita Vishwa Vidyapeetham
    Amritanagar, Coimbatore - 641 112
    Tamilnadu, India