Factorizations of the complete graph into C-5-factors and 1-factors

In this paper, we show that K-10n can be factored into alpha C-5-factors and beta 1-factors for all non-negative integers alpha and beta satisfying 2alpha + beta = 10(n) - 1.

The value of idiosyncratic markers and changes to conserved tRNA sequences from the mitochondrial genome of hard ticks (Acari: Ixodida: Ixodidae) for phylogenetic inference

Idiosyncratic markers are features of genes and genomes that are so unusual that it is unlikely that they evolved more than once in a lineage of organisms. Here we explore further the potential of idiosyncratic markers and changes to typically conserved tRNA sequences for phylogenetic inference. Hard ticks were chosen as the model group because their phylogeny has been studied extensively. Fifty-eight candidate markers from hard ticks ( family Ixodidae) and 22 markers from the subfamily Rhipicephalinae sensu lato were mapped onto phylogenies of these groups. Two of the most interesting markers, features of the secondary structure of two different tRNAs, gave strong support to the hypothesis that species of the Prostriata ( Ixodes spp.) are monophyletic. Previous analyses of genes and morphology did not strongly support this relationship, instead suggesting that the Prostriata is paraphyletic with respect to the Metastriata ( the rest of the hard ticks). Parallel or convergent evolution was not found in the arrangements of mitochondrial genes in ticks nor were there any reversals to the ancestral arthropod character state. Many of the markers identified were phylogenetically informative, whereas others should be informative with study of additional taxa. Idiosyncratic markers and changes to typically conserved nucleotides in tRNAs that are phylogenetically informative were common in this data set, and thus these types of markers might be found in other organisms.

The highly rearranged mitochondrial genome of the plague thrips, Thrips imaginis (Insecta : thysanoptera): Convergence of two novel gene boundaries and an extraordinary arrangement of rRNA genes

To help understand the mechanisms of gene rearrangement in the mitochondrial (mt) genomes of hemipteroid insects, we sequenced the mt genome of the plague thrips, Thrips imaginis (Thysanoptera). This genome is circular, 15,407 by long, and has many unusual features, including (1) rRNA genes inverted and distant from one another, (2) an extra gene for tRNA-Ser, (3) a tRNA-Val lacking a D-arm, (4) two pseudo-tRNA genes, (5) duplicate control regions, and (6) translocations and/or inversions of 24 of the 37 genes. The mechanism of rRNA gene transcription in T. imaginis may be different from that of other arthropods since the two rRNA genes have inverted and are distant from one another. Further, the rRNA genes are not adjacent or even close to either of the two control regions. Tandem duplication and deletion is a plausible model for the evolution of duplicate control regions and for the gene translocations, but intramitochondrial recombination may account for the gene inversions in T. imaginis. All the 18 genes between control regions #1 and #2 have translocated and/or inverted, whereas only six of the 20 genes outside this region have translocated and/or inverted. Moreover, the extra tRNA gene and the two pseudo-tRNA genes are either in this region or immediately adjacent to one of the control regions. These observations suggest that tandem duplication and deletion may be facilitated by the duplicate control regions and may have occurred a number of times in the lineage leading to T. imaginis. T. imaginis shares two novel gene boundaries with a lepidopsocid species from another order of hemipteroid insects, the Psocoptera. The evidence available suggests that these shared gene boundaries evolved by convergence and thus are not informative for the interordinal phylogeny of hemipteroid insects. We discuss the potential of hemipteroid insects as a model system for studies of the evolution of animal rut genomes and outline some fundamental questions that may be addressed with this system.

Rates of gene rearrangement and nucleotide substitution are correlated in the mitochondrial genomes of insects

A number of studies indicated that lineages of animals with high rates of mitochondrial (mt) gene rearrangement might have high rates of mt nucleotide substitution. We chose the hemipteroid assemblage and the Insecta to test the idea that rates of mt gene rearrangement and mt nucleotide substitution are correlated. For this purpose, we sequenced the mt genome of a lepidopsocid from the Psocoptera, the only order of hemipteroid insects for which an entire mtDNA sequence is not available. The mt genome of this lepidopsocid is circular, 16,924 bp long, and contains 37 genes and a putative control region; seven tRNA genes and a protein-coding gene in this genome have changed positions relative to the ancestral arrangement of mt genes of insects. We then compared the relative rates of nucleotide substitution among species from each of the four orders of hemipteroid insects and among the 20 insects whose mt genomes have been sequenced entirely. All comparisons among the hernipteroid insects showed that species with higher rates of gene rearrangement also had significantly higher rates of nucleotide substitution statistically than did species with lower rates of gene rearrangement. In comparisons among the 20 insects, where the mt genomes of the two species differed by more than five breakpoints, the more rearranged species always had a significantly higher rate of nucleotide substitution than the less rearranged species. However, in comparisons where the mt genomes of two species differed by five or less breakpoints, the more rearranged species did not always have a significantly higher rate of nucleotide substitution than the less rearranged species. We tested the statistical significance of the correlation between the rates of mt gene rearrangement and mt nucleotide substitution with nine pairs of insects that were phylogenetically independent from one 2 another. We found that the correlation was positive and statistically significant (R-2 = 0.73, P = 0.01; R-s = 0.67, P < 0.05). We propose that increased rates of nucleotide substitution may lead to increased rates of gene rearrangement in the mt genomes of insects.

Prospects for whole genome linkage disequilibrium mapping in domestic dog breeds

Linkage disequilibrium (LD) mapping is commonly used as a fine mapping tool in human genome mapping and has been used with some success for initial disease gene isolation in certain isolated inbred human populations. An understanding of the population history of domestic dog breeds suggests that LID mapping could be routinely utilized in this species for initial genome-wide scans. Such an approach offers significant advantages over traditional linkage analysis. Here, we demonstrate, using canine copper toxicosis in the Bedlington terrier as the model, that LID mapping could be reasonably expected to be a useful strategy in low-resolution, genome-wide scans in pure-bred dogs. Significant LID was demonstrated over distances up to 33.3 cM. It is very unlikely, for a number of reasons discussed, that this result could be extrapolated to the rest of the genome. It is, however, consistent with the expectation given the population structure of canine breeds and, in this breed at least, with the hypothesis that it may be possible to utilize LID in a genome-wide scan. In this study, LD mapping confirmed the location of the copper toxicosis in Bedlington terrier gene (CT-BT) and was able to do so in a population that was refractory to traditional linkage analysis.

Decompositions of complete graphs into theta graphs with fewer than ten edges

A theta graph is a graph consisting of three pairwise internally disjoint paths with common end points. Methods for decomposing the complete graph K-nu into theta graphs with fewer than ten edges are given.