Welcome!

Ramblings about work on subjects uninteresting to most people.

2015-10-22

Survey: Sage and Enumerative Combinatorics

The project I'm helping out with for nearly two years now is Sage Math, which has 700k lines of Python code that glue about a hundred open source math software packages into one tool conglomerate. My mathematical interest was always discrete math, and the recent developments in symbolic computation fueling the new experimental mathematics fascinate me especially. This made me naturally gravitating towards advancing symbolics in Sage which, I regret to say, is in a poor (unsexy) state because most main developers of Sage are interested in abstract algebra and number theory, but less in enumerative combinatorics, nor in experimental symbolics, or even calculus.

Experimental symbolics is very successful in discrete math, especially enumerative combinatorics. The natural question arises, how far can Sage help with this branch of symbolics? To this end I present a table of respective mathematical objects and algorithms, and the support Sage has for them. I'm leaning heavily on the recent summary of computer algebra relevant for enumerative combinatorics by Manuel Kauers (published in Bona's new Handbook of Combinatorics).

Sage capability survey (Fall 2015)
Computation in/with Status Comments
Finite fields Documentation
Lattice reduction Documentation
Multivariate polynomials Documentation
Gröbner bases Documentation
Algebraic number arithmetic Documentation
Cylindrical Algebraic
Decomposition
Documentation (from Sage version 6.10.p2 up)
Formal power series Two implementations, a fast one missing most symbolic function expansions, and a slower one with function expansions, but neglected having many bugs. Both not interoperating.---Documentation1, Documentation2
Lazy power series rudimentary---Documentation
Laurent series Only univariate available
Puiseux series
Ore algebras optional package ore-algebra
C-finite sequences Documentation
D-finite sequences
Combinatorial species Documentation
Omega analysis (partitions)
Ehrhart theory incomplete, in progress
Computational group theory available via GAP
Symbolic summation: Gosper's algorithm part of sum(), available via Maxima
Zeilberger's algorithm part of sum(), available via Maxima
Petkovšek's algorithm
Karr's algorithm


Creative telescoping
ΠΣ-theory
Holonomic functions


2013-09-21

Random 100 sequences from the OEIS---a survey.

Summary: there were 16 holonomic, 16 prime, 11 digital, 7 constants, 4 arbitrary, 28 number theoretic, 13 combinatorial, four group theoretical, and one physics sequences in a random sample of 100 sequences from the OEIS.

The field I'm feeling most natural is mathematics, and I think my most successful work is associated with the OEIS database of integer sequences which sparked all my papers so far. To get an impression on what type of OEIS entries there are, I decided to work on a random sample of one hundred of them, and try to classify them.

So, let's get a random sample. Welcome to a hundred random numbers between 1 and 229000:
? for(i=1,100,print1(random(229000),","))
  • First, there are polynomials in n, linear recurrences with constant coefficients (or lin-recs as the editors call them frequently), and other holonomic sequences. This is basic stuff, although not completely uninteresting. Many at first really interesting sequences later turn out to be of this type: A004315, A005056, A009671, A012845, A013081, A029920, A070358, A107396, A109794, A132200, A133886, A135493, A140405, A175485, A193931, A213036
  • Then, the sequences involving primes. In my personal opinion most such sequences are random (no formulae possible), and you can't say much about them in terms of conjectures, although they may not be unimportant to have in the database: A003631, A007996, A013637, A022465, A045467, A066520, A086762, A088592, A090725, A100669, A105998, A118812, A120853, A122413, A142247, A188754
  • Sequences involving decimal, and other digits: A034967, A037914, A053974, A061958, A075009, A092995, A095827, A102120, A117860, A141063, A209859
  • A certain amount of OEIS entries are decimal expansions of constants. The justification to include them is the benefit for inverse calculations, and as a point where to collect statements and references about the respective constant: A088543, A153205, A154167, A196505, A196758, A198565, A201848
  • Some sequences are so arbitrary that, although they could be interesting, it would be better to look at a definition or formula with small constants first and generalize from that. If the submitter gives no reason for the importance of such an arbitrary sequence, it is most likely unimportant. I found the following that fit this description: A030835, A040566, A152339, A182771
Now, the rest is what many OEIS editors agree to be interesting.
The really interesting sequences can be divided according to the field of mathematics they arise in, so let me list them so grouped. From here I will give one-liner definitions and make them clickable.

Number theory
A002547 Numerator of {n-th harmonic number H(n) divided by (n+1)}.
A004618 Divisible only by primes congruent to 4 mod 5.
A033831 Number of d dividing n such that d>=3 and 1<=n/d<=d-2.
A049384 a(0)=1, a(n+1) = (n+1)^a(n).
A060553 Symmetric patterns in the cellular automaton that generates Pascal's triangle modulo 2.
A064031 Product of non-unitary divisors of n!. 
A081474 Distinct lines through the origin in n-dimensional cube of side length n.  
A088138 Generalized Gaussian Fibonacci integers.
A088303 Smallest integer value of n!/ ( 1!a!b!c!...) ...
A089552 Sum of legs of primitive Pythagorean triangles having legs that add up to a square, sorted on hypotenuse.
A094234 Period of terms in continued fraction expansion of 2^n*tanh(1).
A117658 Number of solutions to x^(k+1)=x^k mod n for some k>=1.
A120615 sum(k=0,n,floor(phi*floor(n/phi))) where phi=(1+sqrt(5))/2.
A139799 n>=2 such that there is an integer k>1 with k divides n and k divides (n/k)+1.
A140418 Position of cubes in the EKG sequence.
A141321 Special sum of divisors of n.
A152066 Coefficients of certain polynomials.
A160394 Numbers n = p*q*r (p, q, r prime) congruent to 0 mod p+q+r.
A172819 Number of n X 9 0..4 arrays with row sums 9 and column sums n.
A173931 Primitive numbers k such that m/k is in the Cantor set for some m. 
A178272 Number of collinear point 7-tuples in an n X n .. X n 4-dimensional cubical grid.
A178535 Matrix inverse of A178534.
A185383 Denominator of the fraction |n^2/A049417(n)-A064380(n)|.
A189675 Composition of Catalan and Fibonacci numbers.
A200521 Numbers n such that omega(n)=4 but bigomega(n)>4.
A218335 Even numbers n such that the largest value in trajectory of n under the juggler map is greater than n.
A227128 The twisted Euler phi-function for the non-principal Dirichlet character mod 3.
A227434 Value of row n in Pascal's triangle mod 3 seen as ternary number.

Enumerative combinatorics
A028461 Number of perfect matchings in graph P_{3} X C_{4} X P_{n}.
A057545 Maximum cycle size in range...
A124419 Number of partitions of the set {1,2,...n} having no blocks that contain both odd and even entries.
A135493 Number of ways to toss a coin n times and not get a run of six.
A149516 Number of walks within N^3 (the first octant of Z^3) starting...
A183882 Number of arrangements of n+2 numbers in 0..7 with ...
A185334 Number of not necessarily connected 3-regular simple graphs on 2n vertices with girth at least 4.
A186764 Permutations of {1,2,...,n} having k increasing even cycles.
A207224 Number of nX4 0..2 arrays avoiding the patterns ...
A208545 Number of 7-bead necklaces of n colors allowing reversal, with no adjacent beads having the same color.
A211359 Noncrossing partitions up to rotation and reflection of an n-set that contain k singleton blocks.
A214130 Partitions of n into parts congruent to +-2, +-3 (mod 13).
A227189 (k+1)-th part of the unordered partition which has been encoded in the binary expansion of n.

Group theory
A019537 Number of special orbits for dihedral group of degree n.
A057743 Maximal order of element of alternating group A_{2n+1}.
A170263 Number of reduced words of length n in Coxeter group on 14 generators
A214464 Degrees of irreducible representations of Suzuki group Sz(32).

Mathematical physics
A008199 Coordination sequence T4 for Zeolite Code MTW.

So, now you have a pretty good overview of what kind of OEIS entries exist, and what OEIS editors think are interesting submissions. If such pearls as the above can be found in a random sample of 100, what treasures might lurk there in the whole thing? Look for yourself!

2011-09-03

Methionine

This story has three parts: Met salvage, catabolism, and urology. And it spans three decades of missing research.

L-Methionine (Met) is an essential amino acid. Its use is to take part in Met-RNA and protein biosynthesis, and the synthesis of S-Adenosylmethionine (SAM). In all cases it is recycled. Even when SAM is used to produce polyamines, the sulfur is recycled to Met via the Met salvage pathway. However, if you take a Met overdose -- say 1 or 2 grams orally -- the excess doesn't show in the blood for long, and is degraded or changed quickly. It appears to be well known[1] that this excess leads to an excess of sulfate which is excreted with urine. Around 1985, at least two reactions were hypothesized for excess Met -- transamination to 4-methylthio-2-oxobutanoate (MOB) and transmethylation-transsulfuration via SAM, homocysteine and cystathionine -- with inconclusive results on which is the main path[2]. The transamination reaction to MOB certainly plays a role[3] but where the sulfate comes from quantitatively (MOB or cystathionine) is still unclear, as well as the whole regulation issue in such a tightly regulated system. Possibly the location, cytosol or mitochondria, makes a difference. Meanwhile, a review elucidated the cysteine catabolic branch[4]. So, a complete characterization of the Met-catabolic pathway via transamination -- or the proof of it being irrelevant awaits the trophy-hungry lab rat.

Additionally, in the Met salvage pathway, we don't know exactly the human gene producing the necessary methylthioribulose 1-phosphate dehydratase activity (EC 4.2.1.109). From homology to yeast, it might be APIP but the human activity was never shown. And finally, while transamination to and from Met is proven, which of the many transaminases has that broad specificity to also take on Met? Our guess it's the GGT but noone bothered to test it for decades.

Finally, the sulfate excretion accounting for the acidification potential of Met[5], according to my urologist, this is the only compound with that effect on humans. There may be also ammonium chloride (ref?). Okay, there is the n=60 study[6] showing diluted vinegar being effective in urinary tract infection (UTI), but would you drink it daily to prevent infections? Surprisingly, although the beneficial effect of low pH urine for UTI prevention is beyond doubt, there is no clinical study using Met for this. It would be so easy, the pH test strips and Met itself are inexpensive, so please someone take up this piece of Unsexy Science!

Refs:
1.  Mudd, S. H., and H. L. Levy. 1983. Disorders of Transsulfuration. In: The Metabolic Basis of Inherited Disease. 5th edition. J. B. Stanbury, J. B. Wyngaarden, D. S. Fredrickson, J. L. Goldstein, and M. S. Brown, editors. McGraw-Hill Book Co., Inc., New York. 522-559. (unchecked)
2. J. D. Finkelstein, J. J. Martin: Methionine metabolism in mammals. Adaptation to methionine excess. In: J biol chem 261, 4, 1986, 1582–1587. PMID 3080429.
3. W. A. Gahl, I. Bernardini et al.: Transsulfuration in an adult with hepatic methionine adenosyltransferase deficiency. In: J clin. invest. 81, 2, 1988, 390–397. doi:10.1172/JCI113331. PMID 3339126. PMC 329581.
4. M. H. Stipanuk, I. Ueki: Dealing with methionine/homocysteine sulfur: cysteine metabolism to taurine and inorganic sulfur. In: Journal of inherited metabolic disease 34, 1, 2011, 17–32. doi:10.1007/s10545-009-9006-9. PMID 20162368. PMC 290177. (Review)
5. D. L. Bella, M. H. Stipanuk: Effects of protein, methionine, or chloride on acid-base balance and on cysteine catabolism. In: Am J phys 269, 5 Pt 1, 1995, E910–E917. PMID 7491943.
6. Y. C. Chung, H. H. Chen, M. L. Yeh: Vinegar for Decreasing Catheter-Associated Bacteriuria in Long-Term Catheterized Patients : A Randomized Controlled Trial. In: ''Biological research for nursing'' epub 2011. doi:10.1177/1099800411412767. PMID 21708892.

The case of the one hand clapping

Fatty acid synthesis happens alike in all organisms. Like an assembly line parts are hung onto a template until it grows to a long chain. The template is fixed to a bench, the ACP protein domain, and half a dozen enzymes are at work around it, and with recurring activity, to perform the task until the required length results. In one of the steps an acyl moiety is fused to a malonyl moiety and the chain so elongated. Imagine my surprise when I found everywhere the reaction depicted as

acyl-ACP + malonyl-ACP = 3-oxoacyl-ACP + CO2 + ACP         [3]

Twice ACP? That would be fine in mitochondria or bacteria, as there the ACP domain is on a separate protein and, well, let's just take two of them. But in animals' cytosol all enzymatic and ACP domains are on a single enzyme, the fatty acid synthase (FAS). Now, this FAS is a dimer in nature, which could account for the second ACP. Theoretically. We learn from the literature[1] that both monomers are sandwiched in a way that both ACP domains are far apart. Moreover, it is known[2] that the dimer can only contain one phosphopantethein (PPT) per dimer, and this also means, only one usable ACP domain.

Well, I would say one of the ACPs in the reaction actually is CoA in cytosol of animals but who is inclined to show it experimentally? Certainly not the pharma industry. The subject of mostly known physiology is boring, nothing wholly surprising or monetary is to expect. It's all Unsexy Science!

Ref.:
1. A. Witkowski, V. S. Rangan et al.: Structural organization of the multifunctional animal fatty-acid synthase. In: European journal of biochemistry / FEBS 198, Nr 3, June 1991, 571–579. PMID 2050137
2.  A. Jayakumar, M. H. Tai et al.: Human fatty acid synthase: properties and molecular cloning.'' In: ''Proceedings of the National Academy of Sciences of the United States of America'' V 92, Nr 19, September 1995, 8695–8699. PMID 7567999. PMC 41033
3. IUBMB Enzyme Nomenclature, EC 2.3.1.41 Website

About this blog

Half the cup was full when my urologist told me the only medicine that can acidify urine was no longer paid by german health insurance, due to missing evidence of its activity, despite all urologists knowing about it. However, I do not complain about this decision, as it is in line with refusal to pay for quack homeopathics and other nonsense. The second half of the cup filled when I researched physiology data about fatty acid synthesis and found an apparently unrecognized problem. As this is not the first (or even the dozenth) time I find a hole in our physiological knowledge about humans, it finally got me started for a collection of such knowledge holes, as there is no database I could contribute these to.

Now you know what to expect. I am a private biocurator who normally reads papers about the tuberculosis bacterium to create a database that contains physiology knowledge about this organism. Such databases are used by laboratory researchers to make sense of experimental data from microarrays and other high-throughput experiments. So you can say I have an overview. And I see that, frequently, not all experiments are done that would be necessary to elucidate a pathway or process because, admit it, it's just sexier to find something unexpected. This means, however, that researchers rely on others to do the work. This expectation is rarely fulfilled. Which leaves us with knowledge holes. Which ones? Read this blog.