text:
# Past Seminars

## Linking Gene Expression and Regulation by Correspondence Analysis

Speaker: Martin Vingron, Max Planck Institute, Berlin
Date: Thursday, August 7, 2003
Time: 4:00pm-5:00pm
Place: APM 4301
Host: Pavel Pevzner

ABSTRACT
This talk will introduce correspondence analysis as a tool for visualizing associations between genes and conditions in DNA-micro array data. The same technique will also be applied for establishing associations between gene expression data and transcription factor binding sites. While for yeast this can be done based on published transcription factor binding data, for human data we draw on a comparative analysis with mouse data in search for binding sites.

Short Bio: Martin Vingron studied mathematics in Vienna and did his PhD at the EMBL Biocomputing Programme. After postdoctoral work first at the University of Southern California and then at the German National Research Center for Computer Science he became Head of the Theoretical Bioinformatics Division at the German Cancer Research Center in Heidelberg. In 2000 he moved to Berlin to take the position of Director at the Max Planck Institute for Molcular Genetics, heading the Computational Molecular Biology Departement there. He holds a Honorary Professorship at Berlin Free University.
His main research interests lie in sequence analysis and comparison, in the analysis of gene expression data, and in the study of patterns involved in transcriptional regulation.

## Algorithmic Tools for Breaking the Cis-Regulation Code

Speaker: Richard Karp
Date: Monday, May 12, 2003
Time: 4:00pm-5:00pm
Place: APM 4301
Host: Pavel Pevzner

ABSTRACT
Although much computational effort has been devoted to identifying the genes within a genomic sequence, there has been less effort devoted to identifying the regulatory sequence elements that are recognized and bound by transcription factors that control gene transcription. These sequence motifs make up an immensely rich codebook of the gene regulation program, known as the cis-regulatory system. Several recently developed algorithms for finding such motifs use statistical models that take into account specific structural features of transcription factors and their binding sites. We describe one such algorithm, due to Xing, Jordan, Wu and the speaker. Recent findings suggest a modular organization in which sets of trancription factors, binding to sites in a contiguous region of the genome, cooperate in regulating gene expression. We describe algorithms by Sharan,Ovcharenko, Ben-Hur and the speaker for identifying such regulatory modules.

Speaker:  Dr. William Murphy
Date:  January 13, 2003
Time: 4:00pm - 5:00pm
Place: APM Building 4301
Host:  Professor Pavel Pevzner

ABSTRACT
Comparative genomic analysis of mammals offers the potential to interpret the evolutionary dynamics of gene organization within chromosomes, to determine the mechanisms of chromosomal rearrangements, and to reveal the forces governing the conservation of synteny. Major improvements have been made towards understanding the evolutionary relationships and timescale of placental mammal diversification, analyzing large concatenations of nuclear gene segments with maximum likelihood and Bayesian phylogenetic methods. These results emphasize the need for increased large scale genomic analysis from many mammalian lineages to better understand and annotate the human genome. Examining available whole genome maps from representatives of different orders of placental mammals I will discuss evolutionary properties on a chromosomal and whole genome scale, including results based upon multiple genome rearrangement algorithms developed by Pavel Pevzner & colleagues. Using these data we are closing in on determining a probable ancestral genome of placental mammals.

Dr. Murphy received his doctoral degree from the University of Tulsa, where he studied molecular phylogenetics and evolution of tropical killifishes. He entered the Laboratory of Genomic Diversity (LGD) at the National Cancer Institute in Frederick, Maryland as a post-doctoral fellow where he worked on domestic cat comparative genomics under Steve O�Brien. He is currently a research scientist in the LGD working on mammalian phylogenetics and comparative genomics.

## Engineering a Scalable Placement Heuristic for DNA Probe Arrays

Speaker:Dr. Andrew Kahng
Date:December 13, 2002
Time:2pm - 3pm
Place:APM 4301
Host:Pavel Pevzner

ABSTRACT
Design of DNA arrays for very large-scale immobilized polymer synthesis (VLSIPS) seeks to minimize effects of unintended illumination during mask exposure steps. Hannenhalli et al. and Kahng et al. (WABI-2002) formulate this requirement as the Border Minimization Problem and give methods for placement (at array sites) and embedding (in the mask sequence) of probes in both synchronous and asynchronous regimes. These previous methods do not address several practical details of the application and, more critically, are not scalable to the O(10^8) probes contemplated for next-generation probe arrays. In this work, we make two main contributions. (1) We give improved dynamic programming algorithms that perform probe embedding to minimize border conflicts while accounting for distance- and position-dependent border conflict weights, as well as the presence of SNPs in the instance. (2) We describe and experimentally validate the "engineering" of a scalable, high-quality asynchronous placement heuristic (which is moreover embarrassingly parallelizable) for DNA array design. In the process, we draw a number of useful parallels from the 40-year history of placement heuristics in VLSI CAD. Experimental results confirm that our approach enjoys linear-time scaling while maintaining solution quality that matches the best previous methods. This is a joint work with I. I. Mandoiu, P. A. Pevzner, S. Reda and A. Z. Zelikovsky

Short Bio: Andrew B. Kahng is Professor of CSE and ECE at UC San Diego. He joined UCSD in January 2001, after nearly 12 years on the UCLA computer science faculty. His research focuses on physical design and performance analysis of very large-scale integrated circuits (VLSI), as well as the VLSI design-manufacturing interface.

## Perfect Phylogeny Haplotyping

Speaker: Professor Dan Gusfield, Department of Computer Science University of California, Davis
Date: Wednesday, November 27, 2002
Time: 2:15pm - 3:30pm
Place: AP&M Building, Room 4301
Hosts:  Pavel Pevzner and Uri Keich

ABSTRACT
The next high-priority phase of human genomics will involve the development of a full Haplotype Map of the human genome. It will be used in large-scale screens of populations to associate specific haplotypes with specific complex genetic-influenced diseases. However, most studies will collect genotype data rather than haplotype data, requiring the deduction of haplotype information from genotype data. Input to the haplotyping problem is a set of N genotypes, and output is N haplotype pairs that "explain" the genotypes. Several computational approaches to this problem have been developed and used. Most of these use a statistical framework, such as MLE, or statistical computing methods such as EM, Gibbs sampling etc.

We have developed several distinct combinatorial approaches to the haplotyping problem. I will talk about my most recent approach, based on viewing the haplotyping problem in the context of perfect phylogeny. The biological motivation for this is the surprising fact that genomic DNA can be partitioned into long blocks where genetic recombination has been rare, leading to strikingly fewer distinct haplotypes in the population than previously expected. This, along with assumption of infinite sites implies that any "permitted" solution to the haplotyping problem should fit a perfect phylogeny, This is a severe combinatorial constraint on the permitted solutions to the haplotyping problem, and it leads to efficient deterministic algorithms (I will talk about two of them) to deduce all features of the permitted haplotype solution(s) that can be known with certainty. We obtain a) an efficient algorithm to find (if one exists) one permitted solution to the haplotype problem; b) a simple test to determine if it is the unique permitted solution; c) an efficient way to count the number of permitted solutions; d) and an efficient way to implicitly represent the set of all permitted solutions so that each can be efficiently created. As a by-product, we prove that the number of permitted solutions is bounded by 2^k, where k is less than or equal to the number of sites. This is a huge reduction from the number of solutions if we do not require that a solution fit a perfect phylogeny. This implicit representation also allows simple solutions to secondary questions about the genotypes. For example, in the case that the tree is not unique, the representation explicitly reveals which phase relationships (if determined) would reduce the number of possible trees, and gives a conceptual solution to the problem of minimizing the number of haplotype pairs needed to be laboratory-determined in order to deduce the correct tree. We also observe a strong phase-transition (no pun intended) in the probability that a given number of genotypes will be sufficient to uniquely determine the tree. Parts of this work are joint with different collaborators, including R.H. Chung, V. Bafna, G. Lancia, and S. Yooseph

## Progress on Reconstructing Very Large Evolutionary Trees

Speaker: Dr. Tandy Warnow, University of Texas in Austin
Date: Friday, October 4, 2002
Time: 2:00pm - 3:00pm
Place: AP&M Building, Room 4301
Host: Professor Pavel Pevzner

ABSTRACT
Phylogenetic trees, also known as evolutionary trees, model the evolution of biological species or genes from a common ancestor. Reconstructing evolutionary trees is a fundamental research problem in biology, with applications to protein structure and function prediction, pathway detection, sequence alignment, drug design, etc. However, the reconstruction of very large evolutionary trees is exceedingly difficult; not only are the major optimization problems NP-hard, but large real datasets of interest to the biological community can take years of analysis without being solved exactly. Furthermore, while polynomial time methods for phylogeny reconstruction exist, our research shows that the standard approaches (including the popular Neighbor Joining method) may not perform well on large datasets. In this talk I will present new methods which are more suitable to large-scale phylogeny reconstruction. I will describe new dataset decomposition techniques, called Disk-Covering, which can be used in conjunction with any phylogenetic method. We can prove theoretical performance guarantees, with respect to the sequence length required for accuracy, and we can demonstrate improvements in performance with respect to the running time of algorithms for NP-hard optimization problems, such as maximum parsimony and maximum likelihood. If time permits, I will also present results on our research into inferring evolutionary trees from whole genomes.

Short Bio: Tandy Warnow received her PhD in Mathematics in 1991 at UC Berkeley, under the supervision of Eugene Lawler. She spent two years (first as a postdoc for Michael Waterman (USC, Mathematics) and then at Sandia National Laboratories in New Mexico) before joining the faculty at the Uhiversity of Pennsylvania. In 1999 she joined the faculty at the University of Texas at Austin, where she is now an Associate Professor of Computer Sciences, and Co-Director (with David Hillis) for the Center for Computational Biology and Bioinformatics. Tandy received the National Science Foundation Young Investigator Award in 1994, and the David and Lucille Packard Foundation Award in Science and Engineering in 1996.

## Topological Proteomics

Speaker: Dr. Andreas Dress, University of Bielefeld, Germany
Date: Tuesday, September 17, 2002
Time: 4:00pm - 5:00pm
Place: AP&M Building, Room 4301
Host: Pavel Pevzner/Uri Keich

ABSTRACT
"Topological Proteomics" is a new direction of protein-interaction research that has become feasible due to new techniques developed in fluorescence microscopy called "Multi-Epitop Ligand Cartography" or "MELK" for short (see Schubert, W.: Topological Proteomics, Toponomics, MELK-Technology, in M.Hecker & S.Muellner (eds.): Proteomics of Microorganismus: Fundamental Aspects and Application, Springer Series on "Advances in Biochemical Engeneering/Biotechnology", Springer Verlag, Berlin - Heidelberg - New York, in press, and W.Schubert: Polymyositis, Topological Proteomics Technology and Paradigm for Cell Invasion Dynamics. J Theoret Med: Vol. 4 (1), pp 75-84. 2002).

Given a family of proteins (up to 30, say, at present), this technique allows to measure the (relative) concentration p(j) of protein p at locality j (indexed e.g. by pixel coordinates) within a given piece of tissue or blood sample, resulting in as many images with luminosity values p(j) between, say, 0 and 255 as we have proteins under consideration.

One expects that biologically relevant interactions between those proteins will show up in surprisingly large (or small) numbers of localities for which these concentrations exceed some appropriately chosen threshold values simultaneously. From the detection of such linkages between proteins directly at the cellular site of their biological (inter)action, one has been able to identify those proteins (among the given collection of proteins) that were linked to disease. Direct functional linkage analysis in tissue (or blood cells) based on such data is therefore expected to be superior to searching for linkages in "large scale proteomics" expression profiles that are all based upon extraction of proteins from cells and thus upon the destruction of the topological code that encodes the hierarchy of the proteins under consideration.

In the lecture, an illustrative example will be presented, and some software tools and mathematical techniques and problems relating to the task of analyzing MELK data will be discussed.

Short Bio: Born in Berlin/Germany one year before the second world war began into a family that had four its members being murdered in Nazi prisons by the Gestapo in April 1945, survived until today using all sorts of disguises like geometer(1960-63), number theorist (1964-1966), topologist (1967-1969), algebraist (1970-1979), combinatorialist (1980-2000) and, presently, pseudo-biologist.

## Inferring Regulation from Gene Expression with Probabilistic Graphical Models

Speaker: Dr. Nir Friedman, Hebrew University, Jerusalem
Date: Wednesday, August 28, 2002
Time: 3:00pm - 4:00pm
Place: AP&M Building, Room 4301
Host: Professor Pavel Pevzner

ABSTRACT
In recent years, biological and medical research is undergoing a major revolution. High-throughput methods allow to measure and record large amounts of data. In particular, microarray-based hybridization methods techniques allow to simultaneously measure the expression level of thousands of genes. It is clear that such measurements contain information about many different aspects of gene regulation and function. The computational challenge is to extract new biological understanding from this wealth of data. In particular, to gain insight on the "structure" of the interactions between components in the systems, such as genes, proteins, and external signals.

In this talk, I will describe an ongoing project to address this question using probabilistic graphical models. These models represent the measured expression level of each gene as a random variable and each regulatory interaction as a probabilistic dependency between these variables. In this project, we are developing tools for automatic induction of networks from gene expression data, sequence data, and additional high-throughput measurements. We demonstrate the utility of this approach in analysis of several yeast expression data sets. In particular, our method manages to reconstruct fragments of known pathways from such expression profiles, to provide better understanding of combinatorial regulation in complex processes, and to uncover modules of genes sharing a common "program".

Short Bio: Nir Friedman received a B.Sc. in mathematics and computer science from Tel-Aviv University in 1987, a M.Sc. in mathematics and computer science from the Weizmann Institute of Science in 1992, and a Ph.D. in computer science from Stanford in 1997. From 1996 until 1998 , he was a postdoctoral scholar in the computer science division of the University of California at Berkeley. Since the fall of 1998 he is a faculty member at the Computer Science & Engineering School, The Hebrew University of Jerusalem.

Dr. Friedman's major research interests involve learning and inference with probabilistic models and their applications to computational biology. In recent years, he has been extensively working on learning and inference with probabilistic representations of uncertainty. This work mainly focuses on using Bayesian networks for concept learning, data mining, and reinforcement learning. Since he joined the Hebrew University in 1998, Dr. Friedman's research has focused on application of these tools to computational molecular biology. In particular, his group has examined analysis of gene expression data for cancer classification, discovery of novel genes, pathway reconstruction, and understanding of regulatory circuits.

## Identifying Transcription Factor Binding Sites through Markov Chain Optimization

Speaker:Tao Jiang, Department of Computer Science, UC Riverside
Date: Wednesday, May 8, 2002
Time: 1:30 pm
Place: AP&M Building/Room 4301
Host: Uri Keich

ABSTRACT
Even though every cell in an organism contains the same genetic material, each cell does not express the same cohort of genes. Therefore, one of the major problems facing genomic research today is to determine not only which genes are differentially expressed and under what conditions, but also how the expression of those genes is regulated. The first step in determining differential gene expression is the binding of sequence-specific DNA binding proteins ({\it i.e.} {\em transcription factors}) to regulatory regions of the genes ({\it i.e.} {\em promoters} and {\em enhancers}). An important aspect to understanding how a given transcription factor functions is to know the entire gamut of binding sites and subsequently potential target genes that the factor may bind/regulate. In this study, we have developed a computer algorithm to scan genomic databases for transcription factor binding sites, based on a novel Markov chain optimization method, and used it to scan the human genome for sites that bind to {\em hepatocyte nuclear factor 4} $\alpha$ (HNF4$\alpha$). A list of $71$ known HNF4$\alpha$ binding sites from the literature were used to train our Markov chain model. By looking at the window of $600$ nucleotides around the transcription start site of each confirmed gene on the human genome, we identified $849$ sites with varying binding potential and experimentally tested $109$ of those sites for binding to HNF4$\alpha$. Our results show that the program was very successful in identifying $77$ new HNF4$\alpha$ binding sites with varying binding affinities ({\it i.e.} a $71$\% success rate). Therefore, this computational method for searching genomic databases for potential transcription factor binding sites is a powerful tool for investigating mechanisms of differential gene regulation. This is joint work with Kyle Ellrott, Chuhu Yang, and Frances Sladek.

Short Bio: Tao Jiang received a B.S. in Computer Science and Technology from University of Science and Technology of China, Hefei, P.R.China in July 1984 and a Ph.D., in Computer Science, from University of Minnesota in Nov. 1988. He was a faculty member at McMaster University, Hamilton, Ontario, Canada during Jan. 1989 - July 2001. He joined University of California - Riverside as a Professor of Computer Science in Sept. 1999. Tao Jiang's recent research interest includes algorithms, computational molecular biology, computational complexity, and computational aspects of information gathering and retrieval. He has published actively in theoretical computer science and computational biology journals and conferences, and served on program committees for many international conferences as well as review panels for several funding agencies. He is presently serving on the editorial boards of International Journal of Foundations of Computer Science, Journal of Combinatorial Optimization, and Journal of Computer Science and Technology.

## Fast and Accurate Phylogeny Reconstruction Algorithms Based On the Minimum-Evolution Principle

Speaker:Richard Desper, National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, 45 Center Drive, Bethesda, MD, 20892, USA. email: desper@ncbi.nlm.nih.gov
Date: Tuesday, May 7, 2002
Time: 3:30 pm
Place: AP&M Building/Room 4301
Host: Steffen Heber

ABSTRACT
The Minimum Evolution (ME) approach to phylogeny estimation has been shown to be statistically consistent when it is used in conjunction with ordinary least-squares (OLS) fitting of a metric to a tree structure. The traditional approach to using ME has been to start with the Neighbor Joining (NJ) topology for a given matrix, and then do a topological search from that starting point. The first stage requires O(n^3) time, where n is the number of taxa, while the current implementations of the second are in O(pn^3) or more, where p is the number of swaps performed by the program. In this talk, I'll describe a greedy approach to Minimum Evolution which produces a starting topology in O(n^2) time. Also, I'll demonstrate an algorithm that searches for the best topology using nearest neighbor interchanges (NNIs), where the cost of doing p NNIs is O(n^2+pn), i.e. O(n^2) in practice because p is always much smaller than n. The Greedy Minimum Evolution (GME) algorithm, when used in combination with NNIs, produces trees which are fairly close to NJ trees in terms of topological accuracy. Our work also examines ME under a balanced weighting scheme, where sibling subtrees have equal weight, as opposed to the standard "unweighted" OLS, where all taxa have the same weight so that the weight of a subtree is equal to the number of its taxa. The balanced minimum evolution scheme (BME) runs slower than the OLS version, requiring O(n^2 * diam(T)) operations to build the starting tree and $O(pn* diam(T))$ to perform the NNIs, where diam(T) is the topological diameter of the output tree. In the usual Yule-Harding distribution on phylogenetic trees, the diameter expectation is in log(n), so our algorithms are in practice faster that NJ. Furthermore, this BME scheme yields a very significant improvement over NJ and other distance-based algorithms, especially with large trees, in terms of topological accuracy. I will present simulation results which demonstrate that the BME scheme produces output trees which are not only more accurate than those of NJ, but also than slower algorithms such as BioNJ and Weighbor.
This is joint work with: Olivier Gascuel D\'epartement Informatique Fondamentale et Applications, LIRMM, 161 rue Ada, 34392 Montpellier, France Email: gascuel@lirmm.fr

## Sparse Sequence Modeling Applied to Computational Biology and Intrusion Detection

Speaker:Eleazar Eskin
Date: Wednesday, April 17, 2002
Time: 11am - 12pm
Place: AP&M Building/Room 4301
Host: Pavel Pevzner

ABSTRACT
How do we determine what a protein does? What turns genes on and off? Does this system log correspond to a malicious intruder? On the surface, the answers to these three questions seem to have little in common. In fact, these three problems: classifying proteins into families, finding regulatory signals in DNA sequences, and detecting anomalies in audit streams for intrusion detection, can all be characterized as "sparse" sequence modeling problems and addressed in a common framework. In "sparse" sequence modeling problems, only a fraction of the elements of the sequence have relevance to the problem. This is the case in many practical applications, such as the search for regulatory patterns in DNA sequences, where the target of the search is a tiny fraction of the sequence. Similarly, in intrusion detection, typically the evidence that an audit stream from a system contains an attack is often buried in a vast amount of irrelevant information. Furthermore, modeling sparse sequences often requires allowing "softer" matches between a sequence and a canonical model such as allowing for mismatches. A DNA signal, for example "TATAAT", can often occur with several mismatches in any position, in this case as "TAAAAT" or "TATCAT". This presents some serious computational difficulties since there are an exponential number of models which can match a given sequence.

We present a new efficient framework for approaching sparse sequence modeling problems. The framework is grounded in theory and is applied by well engineered implementations to important practical applications. Specifically, we demonstrate this framework on three problems, classification of amino acid sequences into protein families, outlier detection over sequences of system calls for intrusion detection, and signal finding for discovering transcription factor binding sites in gene promoter regions. This framework employs efficient data structures which index the sequences to allow iterating over all possible sparse models of the sequence. We modify several learning algorithms including Boosting, Support Vector Machines, and a new set of outlier detection algorithms to take advantage of this iteration through possible models in our framework. While still considering as rich a set of models as the naive approaches we can avoid the intractable computational difficulties.

The signal finding method is available for public use as a webserver and the intrusion detection methods are currently being transferred into a live deployment.

## Fold recognition - old challenges, new ideas

Speaker: Adam Godzik, Bioinformatics Program, The Burnham Institute and Joint Center for Structural Genomics, UCSD
Date: April 9, Tuesday
Time: 4:00 pm - 5:15 pm
Place: AP&M Building - Room 4301
Host: Pavel Pevzner

ABSTRACT
One of the most interesting problems in sequence analysis is that many proteins with no apparent sequence similarity nevertheless display significant similarity in their structure and function. Are they homologous? Can we make any statements about their evolutionary relations when we are not able to discover any relation between their sequences? Or perhaps we can redefine sequence similarity so it would encompass such unusual pairs.

I present an overview and specific examples of two classes of approaches designed to do the latter. In one, the sequence is redefined as a vector of distributions (profile) and various possibilities of defining and then comparing such vectors lead to different super sensitive algorithms for sequence comparison. The second class of approaches attempts to describe a sequence-structure compatibility function and searches for sequences that would fit into a given structure based on energy criteria.

Despite somewhat shaky theoretical foundations of both groups of algorithms, they become extremely useful in predicting function of newly sequenced proteins and are now used extensively in genome analysis. I present several examples of successes and failures of distant homology recognition.

## Finding Motifs in the Twilight Zone

Speaker:Dr. Uri Keich, Departmment of Computer Science and Engineering, UCSD
Date: Wednesday, April 3, 2002
Time: 1:30 pm
Place: AP&M Building/Room 4301
Host: Pavel Pevzner

ABSTRACT
Gene activity is often affected by binding transcription factors to short fragments in DNA sequences called motifs. Identification of subtle regulatory motifs in a DNA sequence is a difficult pattern recognition problem.

In our talk we will briefly review the computational problem of motif finding and introduce a new motif finding algorithm that can detect very subtle motifs: relying on a generalization of positional profiles to multiprofiles, our MULTIPROFILER algorithm outperforms other leading motif finding algorithms in a number of synthetic models. Moreover, it can be shown that in some previously studied motif models, MULTIPROFILER is capable of pushing the performance envelope to its theoretical limits.

This is joint work with Pavel A. Pevzner.

## Combinatorial Approaches to Finding Motifs in DNA Sequences

Speaker:Dr. Sing-Hoi Sze, Departmment of Computer Science and Engineering, UCSD
Date: Tuesday, March, 26
Time: 3:00 pm
Place: AP&M Building/Room 4301
Host: Pavel Pevzner

ABSTRACT
Motif finding (pattern discovery in unaligned DNA sequences) is a fundamental problem in both computer science and molecular biology with important applications in locating regulatory sites and drug target identification. We describe two combinatorial approaches WINNOWER and SP-STAR which prove to give better performance than some of the most popular signal finding algorithms, including CONSENSUS, GibbsDNA and MEME, when applied to simulated samples with uniform background distribution. We benchmark these and other algorithms on several bacterial and archaeal sites in a setting specifically designed to imitate the situations arising in comparative genomics studies. We then describe a few collaborative projects with biologists to apply these motif finding algorithms to real biological problems. Finally, we describe an ongoing effort to extend SP-STAR to model dyad motifs which consist of two parts with varying distances between the parts.

## Analysis of Cancer Tissue by Complex DNA and Antibody Microarrays

Speaker: Dr. Jörg Hoheisel, Functional Genome Analysis, Deutsches Krebsforschungszentrum (DKFZ), Im Neuenheimer Feld 506, D-69120 Heidelberg, Germany.
Date: Wednesday, March 20
Time: 3:00 pm
Place: San Diego Supercomputer Center (SDSC)
Host: Pavel Pevzner

ABSTRACT
The Division of Functional Genome Analysis at the DKFZ is involved in the development of technologies for the analysis of large genomic areas to entire genomes with respect to the encoded functions and their regulation. Based on technical advances, various functional aspects are being analysed. One emphasis is work on DNA-, protein- and peptide-microarrays. Apart from addressing chemical and biophysical issues, the resulting methods are immediately put to the test in relevant, biologically driven projects on various organisms. Concerning analysis of human material, systems are being developed toward early diagnosis, prognosis and evaluation of the success of disease treatment with accentuation on cancer. Beside a variety of other applications, comparative studies on transcription levels, actual protein expression and epigenetic variation are under way.
URL: http://www.dkfz-heidelberg.de/funct_genome/

## Protein Sequence-Structure Space - New Insights from Combinatorial Extension (CE) Structure Alignment Algorithm

Speaker: Dr. Ilya Shindyalov San Diego Supercomputer Center, University of California, San Diego
Date: March 12, Tuesday
Time: 4:00 pm - 5:15 pm
Place: AP&M Building - Room 4301
Host: Pavel Pevzner

ABSTRACT
A study of sequence-structure space has been performed using the Combinatorial Extension (CE) algorithm for determining structural alignment and BLAST for determining sequence similarity. Significant clusters in sequence-structure space associated with recurrent structures (convergent evolution) and protein superfamilies (divergent evolution) have been described. These observations have been compared to the scop classification of protein domains that defines similar features. Various representations of the PDB as sequence and/or structure non-redundant set of protein chains have been defined. Also comparison between CE and Dali algorithms of the structural alignments is given. Principles for multiple structure alignment and a heuristical algorithm for multiple structure alignment using Monte Carlo approach is described.

## Bioinformatics Classification: Protein Function, Gene Expression and Cancer Subtyping

Speaker: Professor William Stafford Noble, Department of Computer Science, Columbia University
Date: Tuesday, February 19
Time: 4:00 pm - 5:15 pm
Place: AP&M Building - Room 4301
Host: Pavel Pevzner

ABSTRACT
The Computational Biology Laboratory at Columbia University operates at the interface of machine learning, bioinformatics and molecular biology. In this talk, I will describe three ongoing projects in our group.

The first project uses the support vector machine (SVM) learning algorithm to classify proteins by remote homology. A protein amino acid chain is converted into a fixed-length vector by computing a series of p-values from Smith-Waterman pairwise sequence comparisons. The resulting classifier recognizes remote protein homologs from the SCOP hierarchy more accurately than PSI-BLAST, SAM-T98 and the SVM-Fisher method.

The second project addresses a common question in the analysis of DNA microarray data: which classes of genes are most strongly affected by a given set of experimental manipulations? This question falls between unsupervised and supervised analyses, also known as class discovery and class prediction. We introduce three metrics for selecting interesting gene classes from a given library of classes, and we demonstrate their utility on gene expression data sets from yeast, mouse brain and acute leukemias.

In the final part of the talk, I will present preliminary results on the classification and diagnostic prediction of adult soft tissue sarcoma (STS) by gene expression profiling and SVM analysis. STS's are typically classified by phenotypic and genotypic criteria into more than 50 diagnostic categories. SVM analysis allows us to validate and refine these categories, as well as to define robust formal diagnostic classifiers. This project is a collaboration with scientists at the Memorial Sloan-Kettering Cancer Center.

Short Bio: William Stafford Noble (formerly William Noble Grundy) received the Ph.D. in computer science and cognitive science from the University of California, San Diego in 1998, where he studied with Charles Elkan. After one year as a Sloan/DOE Postdoctoral Fellow with David Haussler at the University of California, Santa Cruz, Noble joined the faculty of the Department of Computer Science at Columbia University as an Assistant Professor. He also holds a joint appointment at the Columbia Genome Center. Noble is the recipient of an NSF CAREER award and is a Sloan Research Fellow.

## Multiple Sequence Alignment Using Partial Order Graphs

Speaker: Professor Christopher Lee
Date: Tuesday, November 27th
Time: 3:30 pm - 5:15 pm
Place: AP&M Building - Room 4301
Host: Pavel Pevzner

ABSTRACT
Progressive multiple sequence alignment (MSA) methods depend on reducing an MSA to a linear profile for each alignment step. However, this leads to loss of information needed for accurate alignment, and gap scoring artifacts.

Results: We present a graph representation of an MSA that can itself be aligned directly by pairwise dynamic programming, eliminating the need to reduce the MSA to a profile. This enables our algorithm (POA: partial order alignment) to guarantee that the optimal alignment of each new sequence versus each sequence in the MSA will be considered. Moreover, this algorithm introduces a new edit operator, homologous recombination, important for multidomain sequences. The algorithm has improved speed (linear time complexity) over existing MSA algorithms, enabling construction of massive and complex alignments (e.g., an alignment of 5000 sequences in 4 hours on a Pentium II). We demonstrate the utility of this algorithm on a family of multidomain SH2 proteins, and on EST assemblies containing alternative splicing and polymorphism.

Bio: Dr. Lee is Assistant Professor of Chemistry & Biochemistry at UCLA. His research interests include bioinformatics, coding region polymorphism and alternative splicing. He is a member of the Board of Scientific Counselors for NCBI, and recently received the MIT Technology Review TR100 award. Further information is available at http://www.bioinformatics.ucla.edu/leelab

## Functional MRI of the Medial Temporal Lobe: Visualizing in Flat Space the Neural Components of Memory

Speaker: Dr. Michael Zeineh
Date: Friday, November 16, 2001
Time: 1:10 pm - 2:10 pm
Place: AP&M Building - Room 4301

ABSTRACT
Memory is essential to central nervous system operation. Under the rubric of memory falls the entire history of an organism: updating and accessing this history is vital to an organism's survival. Optimal memory functioning requires that information be quickly and accurately stored, updated, and retrieved. The role of the medial temporal lobe (MTL) in memory processing has been demonstrated by the serious defects in encoding and retrieving new memories in patients and animals with MTL lesions. The MTL consists of several anatomic substructures, namely the hippocampus, amygdala, and adjacent neocortex. Initially, lesion studies found that focal hippocampal lesions impair memory, and larger lesions that encompass adjacent neocortex simply lead to more significant memory impairments. The interpretation was that the hippocampus is the final point of convergence for all declarative memory formation. Recent lesion work, however, has implicated a more complex architecture: anatomically distinct regions may contribute to different components of memory.

Human neuroimaging is an excellent technique to test this hypothesis because the experimenter can query the subject directly and correlate measured brain activity with encoding, recognition, and recall performance. Neuroimaging is based on the phenomenon that blood flow increases to active brain regions. Subsequent modulation of venous blood oxygenation results in signal changes that can be measured using functional magnetic resonance imaging (fMRI). While neuroimaging studies in humans have examined the MTL during a variety of memory conditions, few have specifically measured the differential involvement of its subregions. Using high-resolution fMRI combined with cortical unfolding techniques, our group has examined the activity of cellular compartments within the MTL that contribute to memory formation.

This talk will 1) provide background on the neuroanatomy of memory, 2) describe how functional imaging can be used to measure cerebral activity, 3) detail how we have used cortical unfolding techniques to visual activity within the medial temporal lobe, and 4) demonstrate differential activity within medial temporal substructures observed in memory experiments.

## PatternHunter: Any Genome Anywhere

Speaker: Professor Ming Lin, University of California, Santa Barbara
Date: Friday, October 26, 1001
Time: 11:00 am to 12:00 pm
Place: AP&M Building - Room 4301
Host: Pavel Pevzner

ABSTRACT:
Genomics studies routinely depend on homology searches based on the strategy of finding short seed matches which are then extended. The fast genomic data growth presents a dilemma for Blast-type DNA homology search techniques: increasing seed size decreases sensitivity whereas decreasing seed size slows down computation. For example, in order to process longer sequences, MegaBlast uses seeds of length 28 instead of Blastn's 11. This limits MegaBlast's application to only highly similar sequences. Several other programs based on suffix trees also run at MegaBlast speed and suitable only for highly similar sequences (e.g. MUMmer, Quasar).

We introduce a novel idea for homology search that simultaneously increases sensitivity and search speed. We have implemented this idea in the portable Java program PatternHunter'' that finds homologies within one or between two DNA sequences. Together with many algorithmic improvements, PatternHunter simultaneously exceeds Blastn in sensitivity and alignment quality, MegaBlast in speed (on long sequences), and both in memory use. With a 700+Mhz cpu, its running time ranges from seconds for prokaryotic genomes to minutes for arabidopsis chromosomes to hours for human chromosomes. At sensitivity level equivalent to Blastn seed length 12, PatternHunter processes 9 gigabases of unassembled 3-coverage of mouse genome vs the human genome in 20 cpu-days, for the mouse genome project. Written in Java, it runs any genome anywhere.

Dr. Li is a Professor of Computer Science at University of California at Santa Barbara. His main research interest is bioinformatics. His other research interests include Kolmogorov complexity, machine learning, and analysis of algorithms. He is the author of the book M. Li, P. Vitanyi , "An introduction to Kolmogorov Complexity."

## Improved Shotgun Assembly Techniques for Large Genomes

Speakers: Brian R. Hunt and James A. Yorke, University of Maryland
Date: Tuesday, October 23, 2001
Time: 3:00 to 4:30 pm
Place: AP&M Building Room 4301
Host: Pavel Pevzner

ABSTRACT:
The whole-genome shotgun assembly technique has been remarkably successful in efforts to determine the sequence of base pairs that make up a genome. This technique has required long computation times and/or very large amounts of RAM when applied to large genomes. We describe an approach to shotgun assembly for large genomes such as the mouse, rat, or human that can run efficiently on a computer with 1 or 2 GB of RAM. We describe our methods and results for a crucial step in this direction: the creation of a list of pairs of reads that potentially overlap. A large percentage of the overlaps found by a standard seed-and-extend approach are spurious, due to repeat regions in the genome. Our approach is to reduce the percentage of spurious overlaps in the list to just a few percent before proceeding with assembly. For this task, we use a modified seed-and-extend approach which runs very quickly, followed by an iterative cleaning and error correcting procedure which uses quality values. We also describe methods currently under development to assemble a skeleton of mated read pairs spanning the genome. In particular, we introduce the notion of "chain validation", which further increases the accuracy of both overlap and mate information. We presents preliminary results for all of our techniques applied to a library of 1 million faux reads we created from the C. elegans genome using real quality values.

Brian Hunt is an Associate Professor of Mathematics and James Yorke is a Distinguished University Professor of Mathematics and Physics. Both are affiliated with the Institute for Physical Science and Technology, of which Yorke serves as Director.

## Finding Composite Regulatory Patterns in DNA Sequences

Speaker:  Eleazar Eskin, Department of Computer Science, Columbia University
Time:        3:00 pm, Wednesday , August, 29, 2001
Place:       Applied Physics and Math Building Room 4301
Host:         Pavel Pevzner

ABSTRACT: Pattern discovery in DNA sequences is a fundamental problem in computational biology with important applications in  finding regulatory signals. Current approaches to pattern discovery focus on monad patterns that correspond to relatively short contiguous strings. However, many of the actual regulatory signals are composite patterns that are groups of monad signals. A difficulty in discovering composite signals is that one of the component monad signal in the groups may be too weak". Since the traditional monad-based motif finding algorithms usually output one (or a few) high scoring patterns, they often fail to find composite regulatory signals consisting of weak monad parts. A better approach would be to output a long ranked list (i.e.,
thousands) of top-scoring patterns in a hope that the monad parts belong to this list. We present a new MITRA algorithm for discovering composite signals and several sets of experiments over biological and synthetic data.

## Genes, Permutations and the Common Interval Problem

Speaker: Steffen Heber
Time: 11:00 am, Thursday, May 31, 2001
Place: AP&M Room 4301
Host: Pavel Pevzner

The genome-wide prediction of protein function is an extremely challenging task. For every sequenced genome the role of about half the genes is unknown and most approaches to determine their function are time consuming and expensive.
The availability of a growing number of completely sequenced genomes opens new opportunities for detecting possible functional associations between genes. One approach [Overbeek99,Marcotte99,Snell2000] is based on the observation that genes that repeatedly occur clustered in multiple phylogenetically distant genomes tend to encode functionally interacting proteins, e.g. proteins of a protein complex or proteins of a metabolic pathway. If one models sequenced genomes by permutations of genes, the problem of finding co-occurring genes translates to the combinatorial
problem of finding common intervals in these permutations.
In this talk, we describe an efficient algorithm to solve this problem, and give several lines of future work concerning applications in comparative genomics which promise many interesting bioinformatical questions.

Short Bio: Steffen is a postdoc with Prof. Pevzner. Prior to joining UCSD he worked at the DKFZ (German Cancer Research Centre) in the groups of Prof. Vingron and Dr. Hoheisel.
URL: http:/www.cse.ucsd.edu/~sheber

## COMPUTATIONAL PROTEOMICS AND VIRTUAL LIGAND SCREENING

Speaker: RUBEN ABAGYAN, Department of Molecular Biology, The Scripps Research Institute
Time: 11:00 am, Thursday, May 24, 2001
Place: AP&M Room 4301
Host: Pavel Pevzner

Large scale discovery of new human genes, gene families and isozymes creates an exciting biomedical opportunity. A combination of high throughput efforts to accelerate and automate experimental determination of three-dimensional structures, improved modeling by homology techniques can be employed to generate 3D models for uncharacterized gene family members. Fast fold (or loop) predictions are performed with accurate Poisson electrostatics.

New computational technology for virtual ligand screening allows to generate alternative receptor conformations and perform flexible docking of hundreds of thousands of virtual compounds to the binding site. The success of this technology is demonstrated on several benchmarks and in five experimental projects which tested the prediction results. For well defined binding pockets only about 1% of the initial compound set actually needs to be synthesized and tested.

Short Bio: Dr. Abagyan is a professor at the Department of Molecular Biology, The Scripps Research Institute. Prior to joining Scripps he directed bioinformatics efforts at NYU.
URL: http://abagyan.scripps.edu/ruben.htm

## THE ROLE OF BIOINFORMATICS IN A MICROARRAY EXPERIMENT

Speaker: SEMYON KRUGLYAK, Illumina, San Diego
Time: 11:00 am, Thursday, May 17, 2001
Place: AP&M Room 4301
Host: Pavel Pevzner

The Illumina BeadArray technology is an exciting new platform in the emerging field of microarrays. Applications of microarray technology include SNP genotyping, gene xpression analysis, and proteomics. I will introduce the Illumina platform and describe applications to gene expression. The focus of the talk will be on the role of bioinformatics in an array experiment and the computational challenges that we encounter.

Short Bio: Dr. Kruglyak graduated from Cornell with Ph.D. in Applied Mathematics. His research interests cover DNA sequencing, microsatellite evolution and more recently, the analysis of gene expression data.
URL: http://www.illumina.com/

## ALGORITHMIC STUDY IN COMPUTATIONAL MASS-SPECTROMETRY

Speaker: TIM TING CHEN, University of Southern California
Time: 11:00 am, Thursday, May 3, 2001
Place: AP&M Room 4301
Host: Pavel Pevzner

In recent years, more and more genomes of model organisms have been sequenced. Using these genomic sequences, researchers have made tremendous progress in the study of the genome. Beyond all these successes is the far more challenging and rewarding task of understanding the proteome, the functions of genes and their protein products.

Tandem Mass Spectrometry (MS-MS), which identifies proteins/peptides from their fragmentation mass patterns, is emerging as a powerful technique for the studies of proteins. In this talk, we focus on three fundamental computational problems arisen in proteomic projects:
(1) the peptide identification problem, which finds a peptide sequence that is optimally correlated to a tandem mass spectrum, from a protein or a genomic database,
(2) the de novo peptide sequencing problem, which sequences peptides directly from tandem mass spectra without database search, and
(3) the identification of protein cross-linking sites, which finds a pair of cross-linked peptide sequences optimally correlated to a tandem mass spectrum.
The solution to all these problems requires novel and efficient algorithms, together with practical implementations and data structures.

Short Bio: Dr. Chen is an assistant professor at the Department of Mathematics, Department of Computer Science, and Center for Computational and Experimental Genomics at USC. He was a postdoc research fellow at George M. Church Laboratory at Harvard Medical School. He received his Ph.D. degree in Computer Science from the State University of New York at Stony Brook.
URL: http://hto-13.usc.edu/~tingchen/


text:
# 3 never divides $n^2+1$

Problem: Is it true that 3 never divides $n^2+1$ for every positive integer n? Explain.

Explanation: If n is odd, then $n^2+1$ is even. Hence 3 never divides $n^2+1$, when n is odd.

If n is even, then $n^2+1$ is odd. So 3 could divide $n^2+1$.

And that is where I am stuck. I try to plug in numbers for n but I want a more general form of showing that 3 can't divide $n^2+1$ when n is even.

-
An even number may or may not be divisible by $3$. For example, $6$ is even and divisible by $3$. – Michael Albanese Dec 28 '13 at 4:27
In a similar manner, prove that $5$ never divides $n^2+2$ and $n^2+3$. – Lucian Dec 28 '13 at 5:29

Instead of considering whether $n$ is even or odd, consider the remainder when $n$ is divided by $3$; as an example, if the remainder is $1$, we have $$n = 3k + 1 \implies n^2 + 1 = 9k^2 + 6k + 2$$

which is not divisible by $3$. There are two more cases.

-

Hint: What are the only squares modulo $3$? Put another way, look at the expression $n^{2}+1$ modulo $3$. What is true of $n^{2} \pmod 3$ for any $n \in \mathbb{N}$?

-
But there are three results. that $n^2$ is congruent to 0,1,2 – Username Unknown Dec 28 '13 at 4:29
Can you give me an example of $n$ such that $n^{2} \equiv 2 \pmod 3$? ;) (To prove there is no such $n$, use the fact that congruence classes are multiplicative: for each $n$, $n$ is congruent to $0, 1,$ or $2 \pmod 3$. Then compute $n^{2}$ in each case. $0$ and $1$ are obvious. But $2^{2} = 4 \equiv 1 \pmod 3$) – Alex Wertheim Dec 28 '13 at 4:30

If $3$ divides $n^2+1$ then it must have solution modulo $3$. But clearly

$0^2+1\equiv 1 \pmod 3$

$1^2+1 \equiv 2 \pmod 3$

$2^2+1 \equiv 5 \equiv 2 \pmod 3$

Otherwise put $n=3k,3k+1,3k+2$ and see that $3$ never divides it

-

Another way:  notice that $\,3\,$ divides one of $\ \color{#0a0}{n\!-\!1,\,n,\,n\!+\!1}.\$ Therefore

$\ \ \ \color{#c00}{3\mid n^2\!+1}\Rightarrow\ 3\mid 2 = (\color{#c00}{n^2\!+1})(2\!-\!n^2)+\color{#0a0}{(n\!-\!1)n^2(n\!+\!1)},\$ contradiction.

Remark $\$ The above implies coprime $\,n^2\!+1\,$ and $\,n^3\!-n = (n\!-\!1)n(n\!+\!1),\,$ except when $\,n\,$ is odd, when they have gcd $= 2.\,$ The above linear relation between them is simply the Bezout identity for their gcd, considered as a polynomial over $\Bbb Q$ (which can be computed mechanically using the extended Euclidean algorithm). Though this approach is not as efficient as using modular arithmetic, it highlights an interesting viewpoint that often proves useful: often properties of integers (numbers) are special cases of properties of polynomials (functions).

-

Every integer $n$ can be written in the form $3m+k$, where $m$ is a non-negative integer and $k = 0, 1,$ or $2$. (This is a particular case of the result that for any positive integer $j$, every integer $n$ can be written in the form $jm+k$, where $m$ is a non-negative integer and $k$ is an integer such that $0 \le k < j$.)

Therefore $n^2+1 =(3m+k)^2+1 =9m^2+6mk+k^2+1 =3(3m^2+2mk)+k^2+1$.

If $3 \mid n^2+1$, then $3 \mid k^2+1$. But the possible values of $k^2+1$ are $1, 2,$ and $5$ (for $k = 0, 1, 2$, respectively), and $3$ does not divide any of them.

Therefore $3$ does not divide $n^2+1$.

-

Divide $n$ by $3$ and let $Q$ be the quotient and $R$ the remainder. So

$$n = 3\,Q + R$$ $$n^2+1 = 9\,Q^2 + 6 \, Q\, R + R^2 +1$$ $R$ can only be $0$, or $1$ or $2$. Now argue that in all cases $n^2+1$ is not divisible by $3$.

Not divisibility depends only on $R$ i.e. only on $n \mod 3$. From your question, it looks like you are just starting on number theory. You will soon realize that most problems require you to look only at the remainder.

-

Since $n-1,n,n+1$ are three successive integers so one of them must be divisible by 3 hence there product must be divisible by $3$ i.e. $3|(n-1)n(n+1) \implies 3|n^3-n$ , now

$3|n^2+1 \implies 3|n(n^2+1) \implies 3|n^3+n \implies 3|n^3+n-(n^3-n) \implies 3|2n$ , since 3 does

not divide $2$ so $3|n \implies 3|n^2 \implies 3|n^2+1-n^2 \implies 3|1$ , contradiction !

-

$n= 0 \pmod3 \implies n^2 + 1 = 1\pmod3$,

$n = 1\pmod3 \implies n^2 + 1 = 2\pmod3$,

$n = 2\pmod3 \implies n^2 + 1 = 2\pmod3$.

So $n^2 + 1$ is not a multiple of $3$ for any $n$.

-

Note that the statement mathematically means: $$3 \mid (n^2 + 1) \implies n^2 + 1 \equiv 0 \pmod 3 \equiv n^2 \equiv -1 \equiv 2 \pmod 3.$$ Is this ever possible?

-

If $\delta = 2$, $\delta + 2n + 1 = 2n + 3\quad\imp\pars{n + 1}^{2} + 1 = 3\pars{p + 1} + 2n$: The first term is a multiple of $3$ but the second is even.

-

I agree with all your answers above, but I need someone to point out my error in the following construction;
assume $3|n^2+1$, then we can find an integer $m^2$ such that $n^2+1=3m^2$, so that we arrive at the negative Pell's equation; $n^2-3m^2=-1$, for which there exist infinitely many solutions, showing that m and n actually exist.

-
Just because $3\mid x^2+1$ it does not follow that the quotient should be a square. – Old John Dec 28 '13 at 11:15
Also, that negative Pell equation does not have infinitely many solutions, it has none. – Old John Dec 28 '13 at 11:25
I don't want to put you off, but on this site, an answer isn't meant to be a question itself. – barto Dec 28 '13 at 16:27

format: plain


text:
# univeristy-of-tokyo-eye-catch

### More from my site

• If a Subgroup Contains a Sylow Subgroup, then the Normalizer is the Subgroup itself Let $G$ be a finite group and $P$ be a nontrivial Sylow subgroup of $G$. Let $H$ be a subgroup of $G$ containing the normalizer $N_G(P)$ of $P$ in $G$. Then show that $N_G(H)=H$.   Hint. Use the conjugate part of the Sylow theorem. See the second statement of the […]
• Simple Commutative Relation on Matrices Let $A$ and $B$ are $n \times n$ matrices with real entries. Assume that $A+B$ is invertible. Then show that $A(A+B)^{-1}B=B(A+B)^{-1}A.$ (University of California, Berkeley Qualifying Exam) Proof. Let $P=A+B$. Then $B=P-A$. Using these, we express the given […]
• Eigenvalues and Algebraic/Geometric Multiplicities of Matrix $A+cI$ Let $A$ be an $n \times n$ matrix and let $c$ be a complex number. (a) For each eigenvalue $\lambda$ of $A$, prove that $\lambda+c$ is an eigenvalue of the matrix $A+cI$, where $I$ is the identity matrix. What can you say about the eigenvectors corresponding to […]
• Exponential Functions are Linearly Independent Let $c_1, c_2,\dots, c_n$ be mutually distinct real numbers. Show that exponential functions $e^{c_1x}, e^{c_2x}, \dots, e^{c_nx}$ are linearly independent over $\R$. Hint. Consider a linear combination $a_1 e^{c_1 x}+a_2 e^{c_2x}+\cdots + a_ne^{c_nx}=0.$ […]
• Quiz 4: Inverse Matrix/ Nonsingular Matrix Satisfying a Relation (a) Find the inverse matrix of $A=\begin{bmatrix} 1 & 0 & 1 \\ 1 &0 &0 \\ 2 & 1 & 1 \end{bmatrix}$ if it exists. If you think there is no inverse matrix of $A$, then give a reason. (b) Find a nonsingular $2\times 2$ matrix $A$ such that $A^3=A^2B-3A^2,$ where […]
• Coordinate Vectors and Dimension of Subspaces (Span) Let $V$ be a vector space over $\R$ and let $B$ be a basis of $V$. Let $S=\{v_1, v_2, v_3\}$ be a set of vectors in $V$. If the coordinate vectors of these vectors with respect to the basis $B$ is given as follows, then find the dimension of $V$ and the dimension of the span of […]
• A Group Homomorphism that Factors though Another Group Let $G, H, K$ be groups. Let $f:G\to K$ be a group homomorphism and let $\pi:G\to H$ be a surjective group homomorphism such that the kernel of $\pi$ is included in the kernel of $f$: $\ker(\pi) \subset \ker(f)$. Define a map $\tilde{f}:H\to K$ as follows. For each $h\in H$, […]
• If $R$ is a Noetherian Ring and $f:R\to R’$ is a Surjective Homomorphism, then $R’$ is Noetherian Suppose that $f:R\to R'$ is a surjective ring homomorphism. Prove that if $R$ is a Noetherian ring, then so is $R'$.   Definition. A ring $S$ is Noetherian if for every ascending chain of ideals of $S$ \[I_1 \subset I_2 \subset \cdots \subset I_k \subset […]


text:
# Rotation

## (12) Angular momentum of the system of particles with respect to the center of mass of the system

• let a system of particles is made up of n number of particles.Let ri be the position vector of the ith particle P with respect to a poiint O and vi be its velocity .let Rcm be the position vector of center of mass C of the system with respect to the origin
• Let ri' and vi' be the position vector and velocity vector of the ith particle with respect to center of mass of the system.
• Angular momentum of the system of particles with respect to origin is given by

• Angular momentum of the system of particles with respect to center of mass of the system is given by

Hence the angular momentum of the system of the particles with respect to point O is equal to the sum of the angular momentum of the center of mass of the particles about O and angular monentum of the system about center of mass

(13) Law of conservation of angular momentum
• Torque acting on any particle is given by

If external torque acting on any particle os zero then,

• Hence in absence of external torque the angular momentum of the particle remains constant or conserved.
• Total torque acting on any system is given by

• If total external force acting on any particle system is zero or,

• If total external torque acting on any body is zero , then total angular momentum of the body remains constant or conserved.

Confused and have questions?
Head over to Chegg and use code “CS5OFFBTS18” (exp. 11/30/2018) to get \$5 off your first month of Chegg Study, so you can get step-by-step solutions to your questions from an expert in the field. Plus get a free 30 minute tutoring session.


text:
## Re: proof (mathematical proof?)

Finally!

A very very big thanks to you guys for your help.
It is my first time proving something in math, so it was a very good problem to tackle as it is going to get harder from here...
The teacher don't help too much so it was very fortunate for me to have you explain how to do this right.
Now whats left is for my teacher to check it (and the other problems I solved) and rate it, we'll see how much I get...

Thanks a lot again!


text:
# Integral element

In commutative algebra, an element b of a commutative ring B is said to be integral over A, a subring of B, if there are n ≥ 1 and aj in A such that

${\displaystyle b^{n}+a_{n-1}b^{n-1}+\cdots +a_{1}b+a_{0}=0.}$

That is to say, b is a root of a monic polynomial over A.[1] The set of elements of B that are integral over A is called the integral closure of A in B. It is a subring of B containing A. If every element of B is integral over A, then we say that B is integral over A, or equivalently B is an integral extension of A.

If A, B are fields, then the notions of "integral over" and of an "integral extension" are precisely "algebraic over" and "algebraic extensions" in field theory (since the root of any polynomial is the root of a monic polynomial).

The case of greatest interest in number theory is that of complex numbers integral over Z (e.g., ${\displaystyle {\sqrt {2}}}$ or ${\displaystyle 1+i}$); in this context, the integral elements are usually called algebraic integers. The algebraic integers in a finite extension field k of the rationals Q form a subring of k, called the ring of integers of k, a central object of study in algebraic number theory.

In this article, the term ring will be understood to mean commutative ring with a multiplicative identity.


text:
# Discrete Gaussian Samplers over the Integers¶

This class realizes oracles which returns integers proportionally to $$\exp(-(x-c)^2/(2σ^2))$$. All oracles are implemented using rejection sampling. See DiscreteGaussianDistributionIntegerSampler.__init__() for which algorithms are available.

AUTHORS:

• Martin Albrecht (2014-06-28): initial version

EXAMPLES:

We construct a sampler for the distribution $$D_{3,c}$$ with width $$σ=3$$ and center $$c=0$$:

sage: from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
sage: sigma = 3.0
sage: D = DiscreteGaussianDistributionIntegerSampler(sigma=sigma)

sage: from six.moves import range
sage: n=100000; l = [D() for _ in range(n)]

These are sampled with a probability proportional to $$\exp(-x^2/18)$$. More precisely we have to normalise by dividing by the overall probability over all integers. We use the fact that hitting anything more than 6 standard deviations away is very unlikely and compute:

sage: bound = (6*sigma).floor()
sage: norm_factor = sum([exp(-x^2/(2*sigma^2)) for x in range(-bound,bound+1)])
sage: norm_factor
7.519...

With this normalisation factor, we can now test if our samples follow the expected distribution:

sage: x=0; l.count(x), ZZ(round(n*exp(-x^2/(2*sigma^2))/norm_factor))
(13355, 13298)
sage: x=4; l.count(x), ZZ(round(n*exp(-x^2/(2*sigma^2))/norm_factor))
(5479, 5467)
sage: x=-10; l.count(x), ZZ(round(n*exp(-x^2/(2*sigma^2))/norm_factor))
(53, 51)

We construct an instance with a larger width:

sage: from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
sage: sigma = 127
sage: D = DiscreteGaussianDistributionIntegerSampler(sigma=sigma, algorithm='uniform+online')

sage: from six.moves import range
sage: n=100000; l = [D() for _ in range(n)] # long time

and check if the proportions fit:

sage: x=0;   y=1; float(l.count(x))/l.count(y), exp(-x^2/(2*sigma^2))/exp(-y^2/(2*sigma^2)).n() # long time
(1.0, 1.00...)
sage: x=0; y=-100; float(l.count(x))/l.count(y), exp(-x^2/(2*sigma^2))/exp(-y^2/(2*sigma^2)).n() # long time
(1.32..., 1.36...)

We construct a sampler with $$c\%1 != 0$$:

sage: from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
sage: sigma = 3
sage: D = DiscreteGaussianDistributionIntegerSampler(sigma=sigma, c=1/2)
sage: from six.moves import range
sage: n=100000; l = [D() for _ in range(n)] # long time
sage: mean(l).n() # long time
0.486650000000000

REFERENCES:

class sage.stats.distributions.discrete_gaussian_integer.DiscreteGaussianDistributionIntegerSampler

A Discrete Gaussian Sampler using rejection sampling.

__init__(sigma, c=0, tau=6, algorithm=None, precision='mp')

Construct a new sampler for a discrete Gaussian distribution.

INPUT:

• sigma - samples $$x$$ are accepted with probability proportional to $$\exp(-(x-c)²/(2σ²))$$
• c - the mean of the distribution. The value of c does not have to be an integer. However, some algorithms only support integer-valued c (default: 0)
• tau - samples outside the range $$(⌊c⌉-⌈στ⌉,...,⌊c⌉+⌈στ⌉)$$ are considered to have probability zero. This bound applies to algorithms which sample from the uniform distribution (default: 6)
• algorithm - see list below (default: "uniform+table" for
$$σt$$ bounded by DiscreteGaussianDistributionIntegerSampler.table_cutoff and "uniform+online" for bigger $$στ$$)
• precision - either "mp" for multi-precision where the actual precision used is taken from sigma or "dp" for double precision. In the latter case results are not reproducible. (default: "mp")

ALGORITHMS:

• "uniform+table" - classical rejection sampling, sampling from the uniform distribution and accepted with probability proportional to $$\exp(-(x-c)²/(2σ²))$$ where $$\exp(-(x-c)²/(2σ²))$$ is precomputed and stored in a table. Any real-valued $$c$$ is supported.
• "uniform+logtable" - samples are drawn from a uniform distribution and accepted with probability proportional to $$\exp(-(x-c)²/(2σ²))$$ where $$\exp(-(x-c)²/(2σ²))$$ is computed using logarithmically many calls to Bernoulli distributions. See [DDLL2013] for details. Only integer-valued $$c$$ are supported.
• "uniform+online" - samples are drawn from a uniform distribution and accepted with probability proportional to $$\exp(-(x-c)²/(2σ²))$$ where $$\exp(-(x-c)²/(2σ²))$$ is computed in each invocation. Typically this is very slow. See [DDLL2013] for details. Any real-valued $$c$$ is accepted.
• "sigma2+logtable" - samples are drawn from an easily samplable distribution with $$σ = k·σ_2$$ with $$σ_2 = \sqrt{1/(2\log 2)}$$ and accepted with probability proportional to $$\exp(-(x-c)²/(2σ²))$$ where $$\exp(-(x-c)²/(2σ²))$$ is computed using logarithmically many calls to Bernoulli distributions (but no calls to $$\exp$$). See [DDLL2013] for details. Note that this sampler adjusts $$σ$$ to match $$k·σ_2$$ for some integer $$k$$. Only integer-valued $$c$$ are supported.

EXAMPLES:

sage: from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
sage: DiscreteGaussianDistributionIntegerSampler(3.0, algorithm="uniform+online")
Discrete Gaussian sampler over the Integers with sigma = 3.000000 and c = 0
sage: DiscreteGaussianDistributionIntegerSampler(3.0, algorithm="uniform+table")
Discrete Gaussian sampler over the Integers with sigma = 3.000000 and c = 0
sage: DiscreteGaussianDistributionIntegerSampler(3.0, algorithm="uniform+logtable")
Discrete Gaussian sampler over the Integers with sigma = 3.000000 and c = 0

Note that "sigma2+logtable" adjusts $$σ$$:

sage: DiscreteGaussianDistributionIntegerSampler(3.0, algorithm="sigma2+logtable")
Discrete Gaussian sampler over the Integers with sigma = 3.397287 and c = 0

__call__()

Return a new sample.

EXAMPLES:

sage: from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
sage: DiscreteGaussianDistributionIntegerSampler(3.0, algorithm="uniform+online")()
-3
sage: DiscreteGaussianDistributionIntegerSampler(3.0, algorithm="uniform+table")()
3

algorithm
c
sigma
tau


text:
## Precalculus (6th Edition) Blitzer

The partial fraction is $\frac{1}{\left( x-2 \right)}-\frac{2}{{{\left( x-2 \right)}^{2}}}-\frac{5}{{{\left( x-2 \right)}^{3}}}$
$\frac{{{x}^{2}}-6x+3}{{{\left( x-2 \right)}^{3}}}=\frac{A}{\left( x-2 \right)}+\frac{B}{{{\left( x-2 \right)}^{2}}}+\frac{C}{{{\left( x-2 \right)}^{3}}}$ Now, multiply both sides by ${{\left( x-2 \right)}^{3}}$; then we get, \begin{align} & {{x}^{2}}-6x+3=A{{\left( x-2 \right)}^{2}}+B\left( x-2 \right)+C \\ & =A\left( {{x}^{2}}+4-4x \right)+Bx-2B+C \\ & =A{{x}^{2}}+4A-4Ax+Bx-2B+C \\ & =A{{x}^{2}}+\left( -4A+B \right)x+4A-2B+C \end{align} Then, compare the coefficient of ${{x}^{2}},\ x$ and constant term: $A=1$ …… (1) $-4A+B=-6$ …… (2) $4A-2B+C=3$ …… (3) And put the value of A in equation (2): \begin{align} & -4\left( 1 \right)+B=-6 \\ & B=-6+4 \\ & =-2 \end{align} …… (4) Also, put the value of A and B in equation (3): \begin{align} & 4\left( 1 \right)-2\left( -2 \right)+C=3 \\ & C=3-8 \\ & =-5 \end{align} Therefore, $\frac{{{x}^{2}}-6x+3}{{{\left( x-2 \right)}^{3}}}=\frac{1}{\left( x-2 \right)}-\frac{2}{{{\left( x-2 \right)}^{2}}}-\frac{5}{{{\left( x-2 \right)}^{3}}}$ Thus, the partial fraction of the provided expression is $\frac{1}{\left( x-2 \right)}-\frac{2}{{{\left( x-2 \right)}^{2}}}-\frac{5}{{{\left( x-2 \right)}^{3}}}$.


text:
# 3.2. kwant.builder – High-level construction of systems¶

## Types¶

 Builder([symmetry, conservation_law, …]) A tight binding system defined on a graph. HoppingKind(delta, family_a[, family_b]) A pattern for matching hoppings. BuilderLead(builder, interface[, padding]) A lead made from a Builder with a spatial symmetry. SelfEnergyLead(selfenergy_func, interface, …) A general lead defined by its self energy. ModesLead(modes_func, interface, parameters) A general lead defined by its modes wave functions. FiniteSystem(builder) Finalized Builder with leads. InfiniteSystem(builder[, interface_order]) Finalized infinite system, extracted from a Builder. FiniteVectorizedSystem(builder) Finalized Builder with leads. InfiniteVectorizedSystem(builder[, …]) Finalized infinite system, extracted from a Builder.

## Abstract base classes¶

 Abstract base class for leads that can be attached to a Builder.

## Functions¶

 add_peierls_phase(syst[, peierls_parameter, …]) Add a Peierls phase parameter to a Builder.

## Mixin Classes¶

 Common functionality for all finalized builders Common functionality for all vectorized finalized builders


text:
# How Many Kanbans? – The Kanban Formula, Part 1

One frequent and tricky question when designing a pull system is to determine how many kanbans to use in the system. There are two possible approaches. First, you can calculate the number of kanbans using a kanban formula. Due to the length of the process, I have broken this into two posts (For the second part click here). Alternatively, you can estimate the number of kanbans and adjust the system as it is running (as shown in a third post).

## Kanban Calculation Fundamentals

The number of kanbans defines the performance of a pull system. If you use too few, you will have constant problems with interruptions and missed deliveries or idle workers and processes. If you use too many, you waste space and money for inventory. Of course, if you have the choice between missed deliveries/idle workers or two more parts on the shop floor, I would go for two more parts. Hence in kanban calculations, it is customary to err on the conservative side and, in case of doubt, use more kanbans.

### Factors Influencing the Calculation

Overall, there are five factors that determine the number of kanbans in a system. The first four are rational and are shown in the picture below. The fifth one is not very rational, but it is still needed for the system to work smoothly. These five factors, in the order we will cover them below, are:

1. Regular Time of Customer: How many parts does the customer need in a certain period?
2. Regular Time of Replenishment System: How long does it take to replenish a product in your production or supply system?
3. Fluctuations of Replenishment System: If there are problems in the replenishment system, what problems do we want to cover?
4. Fluctuations of Customer: If  the customer orders more quantity, or the same overall quantity but less frequently, which fluctuations do we want to cover?
5. Safety Margin: Do we want to add additional kanbans so personnel feels more comfortable with the system?

The first two factors will be explained in detail below. The other three factors will be described in the second part of this series of posts on Kanban calculation.

Of course, a major underlying assumption for the kanban calculation is that the system can deliver parts faster than the customer needs them. If your system is too slow, no amount of kanbans will increase your delivery performance. A second assumption is that raw materials for the kanban system are always available.

### Precision of the Kanban Calculation

Kanban formula, kanban calculation … it sounds like physics or science, it all sounds so precise. But let me be very clear on one point: It is not precise! The kanban calculation is nothing more than a very rough estimate using many assumptions. Slightly different but equally valid assumptions may easily change the result by 30% or more. I will point out the assumptions and their effects below to show you the level of precision of the kanban formula.

## Kanban Calculation – Part 1

Below are the mathematical calculations (estimations!) to determine the number of kanbans. Important: You need to calculate this separately for every product type that you want to put in your kanban stock!  Do not calculate this only once for the sum of all product types and then split the kanbans according to volume of the product types. This will not work!

### 1. Regular Time of Customer – Customer Takt

The demand on our kanban system is set by customer demand. The average time between parts ordered by the customer is the basis for converting delays in the system into needed kanbans. We need the so-called customer takt (where takt comes from German and means tact, pulse, or timing). If you have multiple kanban loops in sequence, always take the final customer of the system, not only the demand by the next loop.

To calculate the customer takt, you first need to decide which time period you want to look at. This could be, for example, a week or a month. Then you need to estimate the working hours of your system during this time period. Next you need to estimate the total number of parts delivered to the customer in the future during this time period. The customer takt is now simply the total available working hours of your system divided by the total customer demand during that period. Now you have the average time between the demand for a single product (i.e., your customer takt).

For example, say you decide that you want to look at the next four weeks. During these four weeks, you work five days per week with two shifts of seven hours each. Hence in total you have 280 work hours available during the next four weeks, or 1,008,000 seconds (4 weeks x 5 days x 2 shifts x 7 hours; with 3600 seconds per hour).

You estimate that the future demand by your customer during the next four weeks is 36,000 parts. Dividing your 1,008,000 seconds by 36,000 parts gives you a customer takt of 28 seconds per part. Hence, on average your customer will order one part every 28 seconds.

I mentioned above that the kanban calculation is a very rough estimate. We already have some uncertainty here. Will your system really work 280 hours, or will there be a meeting, a strike, overtime, a day off, or some other interruption? Also, for your customer demand, will the customer really order 36,000 parts? Or will it be more parts due to your customer running out of stock, or less parts if your customers’s demand goes down? All this adds uncertainty. My advice is to make a good estimate, but don’t overdo it. There are much more fuzzy things to come below.

### 2. Regular Time of Replenishment System – Replenishment Time

Next we look at the time needed for one kanban to make a complete circle. If a part is taken out of the supermarket, the kanban is sent back for replenishment. The time between the kanban leaving the supermarket and the kanban coming back to the supermarket attached to a part is hence known as the replenishment time. For our kanban calculations, this replenishment time is needed to estimate the number of kanbans to supply the customer while the supermarket is restocked.

One important part of this replenishment time is the time from the beginning of the actual processing at the first process until the part with the kanban comes back to the supermarket. This time is known as the lead time. For easier understanding, we start our calculations by determining the lead time (i.e., the time for the material flow).

#### 2.1 Lead Time

The lead time can be calculated rather straightforwardly using Little’s Law. Little’s Law, named after its discoverer, John Little, determines (for our purposes) the lead time based on the number of parts in the system and the speed the parts are leaving the system. The law is quite simple, rather precise, and in my view very beautiful.

${ Lead Time = \frac{Inventory}{Throughput}}$

For example, if you have an inventory of 100 parts in the system and the throughput states that there are 10 parts leaving per hour, then the total lead time is 10 hours (100 parts divided by  10 parts per hour). A good example is waiting in a supermarket line. If there are ten people in front of you and on average the check out staff serves two people per minute, then you will have to wait five minutes.

The law is widely valid and quite precise. Unfortunately, the imprecision comes from getting the data, which adds more fluffiness to our very rough estimate. What number to use for the  parts in your system? Of course, you can count them now, but will this still be valid tomorrow? With respect for kanban calculations, I recommend a conservative approach. Take the maximum number of parts that fit in your system (i.e., assume all your FiFo lanes are full and all your machines are loaded to capacity). It may or may not happen, but you still want your kanban system to work when it happens.

Secondly, how fast are your parts leaving the system? Here again you could use different numbers. You could use the inverse of slowest cycle time, or the long-term average throughput, etc. I usually use the long-term average throughput or the inverse of the customer takt (which should be similar anyway). In this way I have also already included fluctuations and losses in the system.

Additionally, you must not forget changeover times. If a kanban arrives at the first process and then has to wait for the set-up (changeover) of the first process, then this time has to be added to the lead time too. If multiple processes in serial or parallel order have changeover time, you have to keep an eye out for overlaps. How much does the lead time increase in total due to changeover times?

Of course, if your lead time includes delays for bulk processing or shipment, you have to take this into account too. For example, if your kanban loop includes shipping from China, then the ship takes two months including customs, no matter how many parts are on the ship. In this case, the lead time would be two months.

#### 2.2 Replenishment Time

The replenishment time now consists of both the time of the material flow (the lead time) and the time for the information flow. Since we just calculated (estimated!) the lead time, we now merely have to determine the time for the kanban from the supermarket to the start of production.

The first part is the waiting time of the kanban at the supermarket after the part has been taken out and the physical movement of the kanban. For example, if every hour a team leader brings the kanban from the collection box at the supermarket to the production, the average waiting time of a kanban at the supermarket would be 30 minutes. However, kanbans can wait up to 60 minutes if a part was taken out of the supermarket just after the team leader collected the cards. Nevertheless, the kanban system still has to work. Hence we assume here the time between pickups as the waiting time at the supermarket.

Secondly, a lot size for production may not only be one kanban but multiple kanbans. For example, if production starts only for a lot size with multiple kanbans, the first kanban has to wait for the remaining kanbans of the lot until a lot is complete and it can be processed. While the average waiting time is shorter, the maximum waiting time is the lot size in kanban minus one. Using a conservative approach, we hence take the maximum waiting time. if your lot size is 10, the waiting time is 9 kanbans; if your lot size is 25, the waiting time is 24 kanbans; and so on. We could now convert the number of kanbans into waiting time, but later on we want to convert the time back into kanbans. Hence, here we keep the waiting time in kanbans to add them later to the kanban total.

Finally, a lot size may not be processed immediately. There already may be other lots waiting for processing before a kanban in the latest lot gets its turn. This is usually a major part of the replenishment time. Unfortunately, this is also very hard to estimate. I have emphasized above that the kanban calculation is only a very rough estimate. This part here is the kicker in terms of imprecision. The waiting time for other lots can fluctuate wildly. What I usually do is assume that for every high-runner product, one lot size (which may be multiple kanbans) is waiting in front of the latest lot.

For example, assume you have 10 types of product, 5 of which are frequent high runners, and each of them has a lot size of 4. In this case, the latest lot may wait for 4 other lot sizes representing 16 kanbans (if it is a high runner too), or 5 other lot sizes representing 20 kanbans (if it is a less frequent exotic part). But again, this is only the roughest of the very rough estimate. Here +/- 30% are easily possible depending on your assumptions. Determining all other factors (customer takt, parts in line, time between parts, etc.) in  high precision is a waste since this estimate negates all this precision. It is almost impossible to get precise data here, but you can’t ignore it since it is a big part of the kanban loop.

As for the lot size above, the waiting time for other lots can be expressed in kanbans, which we could now convert into time just to convert them back later into kanbans. However, my preference is to keep these as kanbans and merely add them to the total later.

In the second post on kanban calculation, I will describe how to include the fluctuations of both our own system and the system on the customer side, before tallying it up and adding the safety margins. The final post will then describe a different approach using kanban estimation and maintenance of the number of kanbans.

### 12 thoughts on “How Many Kanbans? – The Kanban Formula, Part 1”

1. How to define the factory (example garment) need to uses kanban or not? Thanks you!

2. Hello Giang

kanban is one option to make a pull production (another option would be CONWIP). For almost all cases, including garment manufacturing, pull production is superior to push production. Having an upper limit on the WIP gives much better production performance.

Hope this helps,

Chris

3. Hi Giang, this may help (a method we have developed to answer ‘how do you know when to kanban?’)
To identify potential Kanban candidates based upon the three elements (Average demand, Order frequency, Stability of demand), an empirically tested method has been developed:

A part is a candidate for Kanban if all 3 criteria are met:
1. Average weekly demand is over 60 parts per week.
2. Order frequency is over 80%.
3. Demand is stable – One Standard Deviation is less than 100% of average demand.

The figure of 60 parts per week was chosen as a minimum quantity based on the type of components, processes and volumes involved in this particular product range.

Order frequency over 80% means the part was delivered to the customer (in any quantity) during at least 80% of the weeks sampled.

Demand is deemed stable if one standard deviation is less than the average demand value per week (σ < Av weekly demand).

This evaluation has been semi automated into a spreadsheet, drop me a mail and I will send you the 'how to' or check out e-book at
Kanban – Authorising The Flow

Paul.

4. Hi Paul, these numbers seem reasonable for larger parts (Cars, machines, …). Be careful, however, if you produce different products as for example standard screws. 60 screws per week is not much. Personally I also think it depends on the system, in particular its replenishment time, and also the customers willingness to wait. If you can produce everything from scratch while the customer waits, make-to-order using a CONWIP system is the way to go.

5. Hello!
Is it a mistake in the point 2.1 that lead time is a multiplication of inventory (L) and average time between parts (lambda)? According to “A Eulogy for Little’s Law” it should be the quotient…
Regards

6. Hello Małgorzata. Darn, you’re right. Both equations are correct, but throughput is usually defined as parts per time, whereas above I defined it as time per parts, which would be a takt. Using my definition above the equation is correct, but using the “normal” definition of throughput It of course has to be divided by the throughput. Thanks for pointing that out, I have adjusted the post above and now use throughput as parts per time.

7. If you have kanban it means that you don´t have your process connected and you need the tool to balance. Kanban is reflex of a problem!

8. Safety Margin as defined above sounds like permission for a non-formulaic addition of kanban signals. In my experience I expect an acceptable level of kanban failure – or 95% confidence, as it is exponentially more expensive as you approach 100%. Instead of allowing the system to accept these “safety” kanbans, the system failure should be used as an opportunity to become better with 5-why or other problem solving tools. Many times kanban failure is a sign of a healthy kanban system. Furthermore, supermarkets and the related use of kanban should be a temporary solution on the road to further waste elimination. Supermarkets are always sign of kaizan opportunity. What would Taiichi Ohno advise here?

9. Hi Chris, that is exactly what it is – a feel-good factor for the shop floor. I know that tightening the number of kanban helps to find problems on the shop floor. However, in my experience most western shop floors don’t need this help – the problems come all by themselves. Toyota has a) much fewer problems and b) much more manpower for fixing, hence, they can work these problems. In the west, it feels like a constant firefighting with short term fixes because there are too many problems and not enough people. In this case, I rather have enough kanbans so there are not even more problems that I have no time for.

10. The effect required is “smoother and faster flow”. The Ultimate goal is to remove as many kanbans without flow penalty, and move to “MTO”. Kanbans smooth the flow, they provide a buffer between processes. i use 3,6,9 tickets in a kanban. i like thirds. I don’t get to bothered by the start number of parts in a kanban. it sorts itself out quickly. i use kanbans where there are fast runners to medium runners, otherwise, MTO.

11. Hi,

Actually we have below part no’s from production to supermarket

part no Deaily demand Lead time for 10 batch
A 2 5.5 hrs
B 4 5.5 hrs
C 4 5.5 hrs
D 4 5.5 hrs
E 17 5.5 hrs
F 5 5.5 hrs
G 1 5.5 hrs
H 1 5.5 hrs
I 13 5.5 hrs
J 5 5.5 hrs
K 16 5.5 hrs
L 17 5.5 hrs

I wanted to know the details of the Kanban and Heijunka calculation for the above