Patterns in permuted binary matrices

Reorganizing a dataset so that its hidden structure can be observed is useful in any data analysis task. For example, detecting a regularity in a dataset helps us to interpret the data, compress the data, and explain the processes behind the data. We study datasets that come in the form of binary matrices (tables with 0s and 1s). Our goal is to develop automatic methods that bring out certain patterns by permuting the rows and columns. We concentrate on the following patterns in binary matrices: consecutive-ones (C1P), simultaneous consecutive-ones (SC1P), nestedness, k-nestedness, and bandedness. These patterns reflect specific types of interplay and variation between the rows and columns, such as continuity and hierarchies. Furthermore, their combinatorial properties are interlinked, which helps us to develop the theory of binary matrices and efficient algorithms. Indeed, we can detect all these patterns in a binary matrix efficiently, that is, in polynomial time in the size of the matrix. Since real-world datasets often contain noise and errors, we rarely witness perfect patterns. Therefore we also need to assess how far an input matrix is from a pattern: we count the number of flips (from 0s to 1s or vice versa) needed to bring out the perfect pattern in the matrix. Unfortunately, for most patterns it is an NP-complete problem to find the minimum distance to a matrix that has the perfect pattern, which means that the existence of a polynomial-time algorithm is unlikely. To find patterns in datasets with noise, we need methods that are noise-tolerant and work in practical time with large datasets. The theory of binary matrices gives rise to robust heuristics that have good performance with synthetic data and discover easily interpretable structures in real-world datasets: dialectical variation in the spoken Finnish language, division of European locations by the hierarchies found in mammal occurrences, and co-occuring groups in network data. In addition to determining the distance from a dataset to a pattern, we need to determine whether the pattern is significant or a mere occurrence of a random chance. To this end, we use significance testing: we deem a dataset significant if it appears exceptional when compared to datasets generated from a certain null hypothesis. After detecting a significant pattern in a dataset, it is up to domain experts to interpret the results in the terms of the application.

Constructing a Canonical form of a Matrix in Several Problems about Combinatorial Designs

Partially supported by the Bulgarian Science Fund contract with TU Varna, No 487.

A Representation of Binary Matrices

Христина Костадинова, Красимир Йорджев - В статията се обсъжда представянето на произволна бинарна матрица с помощта на последователност от цели неотрицателни числа. Разгледани са някои предимства и недостатъци на това представяне като алтернатива на стандартното, общоприето представяне чрез двумерен масив. Показано е, че представянето на бинарните матрици с помощта на наредени n-торки от естествени числа води до по-бързи алгоритми и до съществена икономия на оперативна памет. Използуван е апарата на обектно-ориентираното програмиране със синтаксиса и семантиката на езика C++.

Ionic liquids and other liquid matrices for sensitive MALDI MS analysis

Although liquid matrix-assisted laser desorption/ionization (MALDI) has been used in mass spectrometry (MS) since the early introduction of MALDI, its substantial lack of sensitivity compared to solid (crystalline) MALDI was for a long time a major hurdle to its analytical competitiveness. In the last decade, this situation has changed with the development of new sensitive liquid matrices, which are often based on a binary matrix acid/base system. Some of these matrices were inspired by the recent progress in ionic liquid research, while others were developed from revisiting previous liquid MALDI work as well as from a combination of these two approaches. As a result, two high-performing liquid matrix classes have been developed, the ionic liquid matrices (ILMs) and the liquid support matrices (LSMs), now allowing MS measurements at a sensitivity level that is very close to the level of solid MALDI and in some cases even surpasses it. This chapter provides some basic information on a selection of highly successful representatives of these new liquid matrices and describes in detail how they are made and applied in MALDI MS analysis.

Análise da variabilidade genética de acessos dePsidium spp. (Myrtaceae) avaliados quanto à reação a Meloidogyne enterolobii

This study aimed to characterize molecular of 13 accessions of Psidium spp. (Myrtaceae) that was been identified for the reaction to rootknot guava nematode. The DNA extraction of the samples was carried according to the protocol of Shillito & Saul (1988). The molecular markers type fAFLP, were obtained from fAFLP Regular Plant Genomes Fingerprinting Kit' (Applied Biosystems from Brasil Ltda.) and were tested 24 selectives combinations of primers, of which 18 showed amplification that produced 272 polymorphic markers. To the analysis of the markers were employed the softwares GeneScan (ABI Prism versao 1.0) and Genotyper (ABI Prism version 1.03), and the data collected were transformed into a binary matrix that was analyzed in the software PAUP (Phylogenetic Analysis Using Parcimony - version 3.01). Were calculated genetic distance index intra and interespecific between the genotipes. It was found that the AFLP markers were efficient in the discrimination between accessions, as well as in showing genetic similarity among accessions identified as resistant to the nematode Meloidogyne enterolobii, which could be discussed in the future.

RAPD analysis of genetic variability in a multiprovenance base population of Eucalyptus grandis hill ex maiden

Este estudo visou avaliar a variabilidade e distância genética dentro de uma população-base de melhoramento genético de Eucalyptus grandis. A avaliação da variabilidade genética tem como objetivos principais analisar a base genética da população-base e montar um banco de dados marcadores moleculares da população em análise. Essa população é formada por 327 indivíduos, principalmente das procedências de Coff's Harbour, Atherton e Rio Claro. Devido à heterozigosidade natural dessa população, ela pode ser dividida em diversas subpopulações, de acordo com a latitude e longitude de origem; e dentro de subpopulações, em função do grau de melhoramento genético já realizado do material analisado no Brasil. Isso permitiu avaliar quanto da variabilidade detectada dentro da população-base foi devido a esses fatores: procedência e grau de melhoramento. A aplicação da técnica RAPD permitiu avaliar 70 locos polimórficos, que foram analisados utilizando-se o coeficiente de Jaccard, o que resultou em matrizes de similaridade genética entre os indivíduos. Os dados de similaridade genética posteriormente foram submetidos à análise estatística. Osdados indicaram que a população-base apresenta ampla base genética, com média de similaridade genética de 0,328. O subgrupo denominado Região 3, composto por material selvagem da macrorregião de Atherton, juntamente com material de APS da macrorregião de Coff's Harbour, foi um dos que mais contribuíram para a ampla base genética da população-base. Foi possível detectar diferença estatística entre as populações selvagens das procedências de Atherton e Coff's Harbour, assim como entre essas procedências e a de Rio Claro.

A comparative floristic analysis of a cerrado area in Botucatu, State of São Paulo (Brazil)

Based on the results of a phytosociological survey in a ''cerrado'' area located within the municipality of Botucatu, state of São Paulo Brazil, a comparative analysis of the 58 sampled tree species' is here presented using the data of other available floristics works for the ''cerrados in the same state. With a binary matrix of presence/absence of shared common species with the studied plot, a clustering analysis was performed thus obtaining a dendrogram which groups northern and southern areas with the same vegetation in the state of São Paulo previously treated as floristicaly differentiated. These results are discussed under the assumption that Isolated areas of ''cerrados'' are to be taken as targets for immediate conservation.

Optimal single-embryo mass spectrometry fingerprinting

In pre-implantation embryos, lipids play key roles in determining viability, cryopreservation and implantation properties, but often their analysis is analytically challenging because of the few picograms of analytes present in each of them. Matrix-assisted laser desorption/ionization mass spectrometry (MALDI-MS) allows obtaining individual phospholipid profiles of these microscopic organisms. This technique is sensitive enough to enable analysis of individual intact embryos and monitoring the changes in membrane lipid composition in the early stages of development serving as screening method for studies of biology and biotechnologies of reproduction. This article introduces an improved, more comprehensive MALDI-MS lipid fingerprinting approach that considerably increases the lipid information obtained from a single embryo. Using bovine embryos as a biological model, we have also tested optimal sample storage and handling conditions before the MALDI-MS analysis. Improved information at the molecular level is provided by the use of a binary matrix that enables phosphatidylcholines, sphingomyelins, phosphatidylserines, phosphatidylinositols and phosphoethanolamines to be detected via MALDI(±)-MS in both the positive and negative ion modes. An optimal MALDI-MS protocol for lipidomic monitoring of a single intact embryo is therefore reported with potential applications in human and animal reproduction, cell development and stem cell research. Copyright © 2013 John Wiley & Sons, Ltd. Copyright © 2013 John Wiley & Sons, Ltd.

Caracterização genética de avestruzes (Struthio camelus) usando marcadores RAPD

O objetivo deste trabalho foi avaliar a variabilidade genética de populações de avestruzes (Struthio camelus) por meio de marcadores RAPD (Polimorfismos de DNA amplificado ao acaso). Foram coletadas 121 amostras de indivíduos procedentes dos estados do Pará, Maranhão, Tocantins e Minas Gerais. O DNA genômico foi extraído a partir de sangue total. A triagem de iniciadores permitiu a seleção de 15 entre os 60 analisados que foram amplificados pelo método PCR. Os produtos da PCR foram visualizados em gel de agarose 1,5% e foi gerada uma matriz binária para os fragmentos amplificados com presença (1) e ausência (0) de banda. Para a verificação do número ótimo de bandas polimórficas foi realizada a análise de bootstrap por meio do software GQMOL. Para a análise dos dados foi utilizado o programa NTSYS-pc (Numerical Taxonomy and Multivariate Analysis Sistem), versão 2.02. A similaridade entre as amostras foi analisada através do coeficiente de Jaccard. Foi gerada uma matriz de distância cofenética, usando o módulo Sahncof, do programa NTSYS 2.2. Para realização da estruturação gênica o procedimento empregado foi a análise de variância molecular (AMOVA), processada no software Arlequin 2.0 (Schneider et al., 2000). Os 15 iniciadores geraram um total de 109 bandas polimórficas. A análise de bootstrap mostrou que a partir de 100 bandas o trabalho já se torna mais confiável, uma vez que a magnitude da correlação foi bem próxima do valor máximo (r=0,99), como também a soma de quadrados dos desvios (SQd) atingiu valor baixo 1,25 e o valor do estresse (E) foi de 0,05. Na análise entre pares de grupos, foi verificado que a maior e menor similaridade estão em torno, respectivamente, de 0,86 e 0,00. No que diz respeito à distribuição de freqüência das similaridades obtidas entre os 5.644 pares formados na matriz genética, pode-se verificar que 32,69 % dos pares ficaram incluídos nas classes com similaridades variando de 0,01 a 0,10. Nota-se que a maior porcentagem (85,59%) dos pares ficou distribuídos nas três primeiras classes das extremidades e que a minoria deles (14,41%) apresentou similaridades variando de 0,21 a 1,00. O teste de Mantel mostrou correlação de 0,81 e o dendrograma gerou 67 grupos delimitados pela Sm que foi de 0,49. A maior similaridade foi de 0,86 e a menor de 0,06. Os dados relativos à análise de variância molecular mostraram que a porcentagem de variação genética entre procedências foi baixa e significativa (24,03%, p < 0,0001), evidenciando que grande parte da variação encontra-se dentro das populações (75,97 %). Os marcadores RAPD foram eficientes na caracterização da similaridade genética.

Metodi molecolari nello studio della variabilità genetica di Tuber borchii

Tuber borchii (Ascomycota, order Pezizales) is highly valued truffle sold in local markets in Italy. Despite its economic importance, knowledge on its distribution and population variation is scarce. The objective of this work was to investigate the evolutionary forces shaping the genetic structure of this fungus using coalescent and phylogenetic methods to reconstruct the evolutionary history of populations in Italy. To assess population structure, 61 specimens were collected from 11 different Provinces of Italy. Sampling was stratified across hosts and habitats to maximize coverage in native oak and pine stands and both mychorrizae and fruiting bodies were collected. Samples were identified considering anatomo-morphological characters. DNA was extracted and both multilocus (AFLP) and single-locus (18 loci from rDNA, nDNA, and mtDNA) approaches were used to look for polymorphisms. Screening AFLP profiles, both Jaccard and Dice coefficients of similarity were utilized to transform binary matrix into a distance matrix and then to desume Neighbour-Joining trees. Though these are only preliminary examinations, phylogenetic trees were totally concordant with those deriving from single locus analyses. Phylogenetic analyses of the nuclear loci were performed using maximum likelihood with PAUP and a combined phylogenetic inference, using Bayesian estimation with all nuclear gene regions, was carried out. To reconstruct the evolutionary history, we estimated recurrent migration, migration across the history of the sample, and estimated the mutation and approximate age of mutations in each tree using SNAP Workbench. The combined phylogenetic tree using Bayesian estimation suggests that there are two main haplotypes that are difficult to be differentiated on the basis of morphology, of ecological parameters and symbiontic tree. Between these two lineages, that occur in sympatry within T. borchii populations, there is no evidence of recurrent migration. However, migration over the history of the sample was asymmetrical suggesting that isolation was a result of interrupted gene flow followed by range expansion. Low levels of divergence between the haplotypes indicate that there are likely to be two cryptic species within the T. borchii population sampled. Our results suggest that isolation between populations of T. borchii could have led to reproductive isolation between two lineages. This isolation is likely due to sympatric speciation caused by a multiple colonization from different refugia or a recent isolation. In attempting to determinate whether these haplotypes represent separate species or a partition of the same species we applied Biological and Mechanistic species Concepts. Notwithstanding, further analyses are necessary to evaluate if selection favoured premating or post-mating isolation.

Mathematical Modeling of the Weaving Structure Design

Красимир Йорджев, Христина Костадинова - В работата се разглежда една релация на еквивалентност в множеството от всички квадратни бинарни матрици. Обсъдена е комбинаторната задача за намиране мощността и елементите на фактормножеството относно тази релация. Разгледана е и възможността за получаване на някои специални елементи на това фактормножество. Предложен е алгоритъм за решаване на поставените задачи. Получените в статията резултати намират приложение при описанието топологията на различните тъкачни структури.

Representing Equivalence Problems for Combinatorial Objects

Methods for representing equivalence problems of various combinatorial objects as graphs or binary matrices are considered. Such representations can be used for isomorphism testing in classification or generation algorithms. Often it is easier to consider a graph or a binary matrix isomorphism problem than to implement heavy algorithms depending especially on particular combinatorial objects. Moreover, there already exist well tested algorithms for the graph isomorphism problem (nauty) and the binary matrix isomorphism problem as well (Q-Extension). ACM Computing Classification System (1998): F.2.1, G.4.

Spatial neighborhood matrix computation: Inverse distance weighted versus binary contiguity

Paper presented at Geo-Spatial Crossroad GI_Forum, Salzburg, Austria.

Generator Matrix Based Search for Extremal Self-Dual Binary Error-Correcting Codes

Self-dual doubly even linear binary error-correcting codes, often referred to as Type II codes, are codes closely related to many combinatorial structures such as 5-designs. Extremal codes are codes that have the largest possible minimum distance for a given length and dimension. The existence of an extremal (72,36,16) Type II code is still open. Previous results show that the automorphism group of a putative code C with the aforementioned properties has order 5 or dividing 24. In this work, we present a method and the results of an exhaustive search showing that such a code C cannot admit an automorphism group Z6. In addition, we present so far unpublished construction of the extended Golay code by P. Becker. We generalize the notion and provide example of another Type II code that can be obtained in this fashion. Consequently, we relate Becker's construction to the construction of binary Type II codes from codes over GF(2^r) via the Gray map.

Calculation of GFSR pseudorandom number binary starting matrix,

Mode of access: Internet.