Search

Your search keyword '"partition tree"' showing total 98 results
Start Over Descriptor "partition tree"
98 results on '"partition tree"'

1. phyBWT2: phylogeny reconstruction via eBWT positional clustering

Author

Veronica Guerrini, Alessio Conte, Roberto Grossi, Gianni Liti, Giovanna Rosone, and Lorenzo Tattini

Subjects
Phylogeny, Partition tree, BWT, Positional cluster, Alignment-free, Reference-free, Biology (General), QH301-705.5, Genetics, QH426-470
Abstract

Abstract Background Molecular phylogenetics studies the evolutionary relationships among the individuals of a population through their biological sequences. It may provide insights about the origin and the evolution of viral diseases, or highlight complex evolutionary trajectories. A key task is inferring phylogenetic trees from any type of sequencing data, including raw short reads. Yet, several tools require pre-processed input data e.g. from complex computational pipelines based on de novo assembly or from mappings against a reference genome. As sequencing technologies keep becoming cheaper, this puts increasing pressure on designing methods that perform analysis directly on their outputs. From this viewpoint, there is a growing interest in alignment-, assembly-, and reference-free methods that could work on several data including raw reads data. Results We present phyBWT2, a newly improved version of phyBWT (Guerrini et al. in 22nd International Workshop on Algorithms in Bioinformatics (WABI) 242:23–12319, 2022). Both of them directly reconstruct phylogenetic trees bypassing both the alignment against a reference genome and de novo assembly. They exploit the combinatorial properties of the extended Burrows-Wheeler Transform (eBWT) and the corresponding eBWT positional clustering framework to detect relevant blocks of the longest shared substrings of varying length (unlike the k-mer-based approaches that need to fix the length k a priori). As a result, they provide novel alignment-, assembly-, and reference-free methods that build partition trees without relying on the pairwise comparison of sequences, thus avoiding to use a distance matrix to infer phylogeny. In addition, phyBWT2 outperforms phyBWT in terms of running time, as the former reconstructs phylogenetic trees step-by-step by considering multiple partitions, instead of just one partition at a time, as previously done by the latter. Conclusions Based on the results of the experiments on sequencing data, we conclude that our method can produce trees of quality comparable to the benchmark phylogeny by handling datasets of different types (short reads, contigs, or entire genomes). Overall, the experiments confirm the effectiveness of phyBWT2 that improves the performance of its previous version phyBWT, while preserving the accuracy of the results.

Published
2023
Full Text
View/download PDF

2. phyBWT2: phylogeny reconstruction via eBWT positional clustering.

Author

Guerrini, Veronica, Conte, Alessio, Grossi, Roberto, Liti, Gianni, Rosone, Giovanna, and Tattini, Lorenzo

Subjects
*MOLECULAR phylogeny, *PHYLOGENY, *VIRUS diseases, *NUCLEOTIDE sequencing
Abstract

Background: Molecular phylogenetics studies the evolutionary relationships among the individuals of a population through their biological sequences. It may provide insights about the origin and the evolution of viral diseases, or highlight complex evolutionary trajectories. A key task is inferring phylogenetic trees from any type of sequencing data, including raw short reads. Yet, several tools require pre-processed input data e.g. from complex computational pipelines based on de novo assembly or from mappings against a reference genome. As sequencing technologies keep becoming cheaper, this puts increasing pressure on designing methods that perform analysis directly on their outputs. From this viewpoint, there is a growing interest in alignment-, assembly-, and reference-free methods that could work on several data including raw reads data. Results: We present phyBWT2, a newly improved version of phyBWT (Guerrini et al. in 22nd International Workshop on Algorithms in Bioinformatics (WABI) 242:23–12319, 2022). Both of them directly reconstruct phylogenetic trees bypassing both the alignment against a reference genome and de novo assembly. They exploit the combinatorial properties of the extended Burrows-Wheeler Transform (eBWT) and the corresponding eBWT positional clustering framework to detect relevant blocks of the longest shared substrings of varying length (unlike the k-mer-based approaches that need to fix the length k a priori). As a result, they provide novel alignment-, assembly-, and reference-free methods that build partition trees without relying on the pairwise comparison of sequences, thus avoiding to use a distance matrix to infer phylogeny. In addition, phyBWT2 outperforms phyBWT in terms of running time, as the former reconstructs phylogenetic trees step-by-step by considering multiple partitions, instead of just one partition at a time, as previously done by the latter. Conclusions: Based on the results of the experiments on sequencing data, we conclude that our method can produce trees of quality comparable to the benchmark phylogeny by handling datasets of different types (short reads, contigs, or entire genomes). Overall, the experiments confirm the effectiveness of phyBWT2 that improves the performance of its previous version phyBWT, while preserving the accuracy of the results. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

3. Partitions, their classes, and multicolour evenness.

Author

Douthett, Jack, Steinbach, Peter, Peck, Robert, and Krantz, Richard

Subjects
ORBITS (Astronomy), INTEGERS, COLOR, ALGORITHMS
Abstract

We extend the theory of maximally even sets to determine the evenness of partitions of the chromatic universe U c . Interactions measure the average evenness of colour sets (partitioning sets) of U c . For 2-colour partitions the Clough-Douthett maximal-evenness algorithm determines maximally even partitions. But to measure the evenness of non-maximally even partitions, it is necessary to use computational methods. Moreover, for more than two colour sets there is no simple algorithm that determines maximally even partitions. Again, we rely on computational methods. We also explore collections of partitions and partition-classes (orbits under a dihedral group) and construct tables that order partition-classes according to the evenness of their partitions. We use Bell numbers, Stirling numbers of the second kind, and integer partitions to enumerate relevant combinatorial objects related to our investigation. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

4. Evaluation of Advanced Analysis Method for Human Relationship Using Fuzzy Theory

Author

Yoshizumi, Toshihiro, Sumida, Tomoo, Shiono, Yasunori, Namekawa, Mitsuhiro, Tsuchida, Kensei, Kacprzyk, Janusz, Series Editor, Pal, Nikhil R., Advisory Editor, Bello Perez, Rafael, Advisory Editor, Corchado, Emilio S., Advisory Editor, Hagras, Hani, Advisory Editor, Kóczy, László T., Advisory Editor, Kreinovich, Vladik, Advisory Editor, Lin, Chin-Teng, Advisory Editor, Lu, Jie, Advisory Editor, Melin, Patricia, Advisory Editor, Nedjah, Nadia, Advisory Editor, Nguyen, Ngoc Thanh, Advisory Editor, Wang, Jun, Advisory Editor, Abraham, Ajith, editor, Cherukuri, Aswani Kumar, editor, and Gandhi, Niketa, editor

Published
2020
Full Text
View/download PDF

5. A new hybrid GPU-CPU sparse LDLT factorization algorithm with GPU and CPU factorizing concurrently.

Author

Liu, Yunmou, Du, Hui, Li, Zhuogen, and Chen, Pu

Subjects
FACTORIZATION, ALGORITHMS, GRAPHICS processing units, LOW density lipoproteins, PARALLEL algorithms
Abstract

This paper proposes a new task assignment scheme for sparse LDL T factorization on a hybrid GPU-CPU platform, and correspondingly an efficient supernodal algorithm, GPU Node and CPU Pipelining (GNCP). GNCP assigns a large number of weakly coupled tasks to GPU and CPU respectively so that GPU and CPU can execute different factorization tasks concurrently without explicit synchronization, which has not been achieved by previous researches. More precisely, based on the number of CPU threads, the global memory of GPU as well the size of the matrix, we introduce the concept of the truncation level in the partition tree built by the multi-level graph partitioning. The sum of FLOP associated with decoupled nodes in the truncation level accounts for about 65% of the whole computations in tested numerical examples. GNCP assigns the factorization tasks of each node in the truncation level to GPU. The data of each node in the truncation level are copied to the global memory of GPU and factorized entirely and independently by GPU one-by-one. Once factorization of any node in the truncation level has been completed, the cross-factorizations of this node to its ancestors and the following related operations are decoupled from other GPU tasks. These tasks are assigned to CPU threads with a reentrant pipelining strategy, accounting for about 35% of the whole calculations. Using this novel design, CPU and GPU are working concurrently and a large part of factorization is performed in overlapped time. Numerical tests for matrices from SuiteSparse matrix collection show higher performance than the well-known hybrid GPU-CPU solver CHOLMOD. • Proposing a new hybrid GPU-CPU sparse LDL T algorithm, GPU Node and CPU Pipelining (GNCP). • In GNCP , GPU and CPU execute different tasks concurrently without explicit synchronization. • Proposing a task assignment scheme that GPU and CPU take about 65% and 35%, respectively. • GPU Node is an efficient GPU LDL T algorithm with a kernel integrating many fragmental GEMMs. • Enriching CPU pipelining parallelism to adapt to hybrid GPU-CPU LDL T algorithm. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

6. SANe: Space adaptation network for temporal knowledge graph completion.

Author

Li, Yancong, Zhang, Xiaoming, Zhang, Bo, Huang, Feiran, Chen, Xiaopeng, Lu, Ming, and Ma, Shuai

Subjects
*KNOWLEDGE graphs, *CONVOLUTIONAL neural networks, *TIME-varying networks, *TIMESTAMPS
Abstract

Temporal Knowledge Graphs (TKGs) model time-dependent facts as relations between entities at specific timestamps, making them well-suited for real-world scenarios. However, TKGs are susceptible to incompleteness, necessitating Temporal Knowledge Graph Completion (TKGC) to predict missing facts. Prior methods often struggle to effectively handle two critical properties of TKGs, time-variability and time-stability, simultaneously, which hinders their performance. In this paper, we propose Space Adaptation Network (SANe), a novel approach for TKGC. SANe adapts facts at different timestamps to distinct latent spaces, effectively addressing time-variability. Our model introduces Parameter Generation Network to produce separate neural networks for each snapshot, which are then encoded into different latent spaces. A dynamic convolutional neural network processes entities and relations, utilizing different learned parameters generated by parameter generation network with respect to timestamps. By handling different temporal snapshots separately, TKGC is transformed into static KGC, enabling the modeling of time-variability. Dynamic convolutional neural network efficiently learns collective knowledge over large periods and supplements more specific knowledge gradually in smaller periods, facilitating time-stability. To strike a balance between learning time-variability and time-stability, we introduce a time-aware parameter generator to produce parameters hierarchically based on year, month, and day timestamps. Long-term knowledge is effectively shared across adjacent snapshots within the same year or month, while short-term knowledge within a day is preserved in specific parameters. However, in unbalanced TKGs, where many facts occur in small intervals, the large number of parameters generated by time-aware parameter generator may remain underutilized. To address this, we propose Adaptive Parameter Generation with a partition tree, ensuring parameter load balancing while maintaining time-stability. We conduct extensive experiments on five benchmark datasets, demonstrating the superiority of SANe over existing methods for TKGC, achieving state-of-the-art performance. Our contributions include pioneering TKGC from the perspective of space adaptation, achieving a balance between time-variability and time-stability through latent space overlap constraints, and substantiating the effectiveness of our model through comprehensive experiments on rich temporal datasets. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

7. Advice Complexity

Author

Komm, Dennis, Henzinger, Monika, Series editor, Hromkovič, Juraj, Series editor, Nielsen, Mogens, Series editor, Rozenberg, Grzegorz, Series editor, Salomaa, Arto, Series editor, and Komm, Dennis

Published
2016
Full Text
View/download PDF

8. Reference Point Hyperplane Trees

Author

Connor, Richard, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Amsaleg, Laurent, editor, Houle, Michael E., editor, and Schubert, Erich, editor

Published
2016
Full Text
View/download PDF

9. Tensor Spaces and Hierarchical Tensor Representations

Author

Hackbusch, Wolfgang, Schneider, Reinhold, Barth, Timothy J., Series editor, Griebel, Michael, Series editor, Keyes, David E., Series editor, Nieminen, Risto M., Series editor, Roose, Dirk, Series editor, Schlick, Tamar, Series editor, Dahlke, Stephan, editor, Dahmen, Wolfgang, editor, Hackbusch, Wolfgang, editor, Ritter, Klaus, editor, Schneider, Reinhold, editor, Schwab, Christoph, editor, and Yserentant, Harry, editor

Published
2014
Full Text
View/download PDF

10. Query Retrieval of Combinations with Sum-of-Subsets Ranking

Author

Majumder, Subhashis, Sanyal, Biswajit, Gupta, Prosenjit, Sinha, Soumik, Pande, Shiladitya, Hon, Wing-Kai, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Zhang, Zhao, editor, Wu, Lidong, editor, Xu, Wen, editor, and Du, Ding-Zhu, editor

Published
2014
Full Text
View/download PDF

11. Analysis indices of human relationships based on fuzzy model.

Author

Yoshizumi, Toshihiro, Sumida, Tomoo, Shiono, Yasunori, Namekawa, Mitsuhiro, and Tsuchida, Kensei

Subjects
*SCHOOL children, *SOCIAL network analysis, *SOCIOMETRY, *INFORMATION science, *PARTITIONS (Mathematics)
Abstract

The purpose of our study is to evaluate an analysis indices and fuzzy decision method for human relationships using fuzzy models. Many studies have been conducted on human relationship analysis in various fields which are sociology, psychology, information science and so on. Most popular analysis method in sociology is sociometry analysis. It was proposed by Moreno. Sociometry analysis is a general method for social network analysis and this method is used in various studies. Sumida has detailed results by studying a group of elementary school students from the perspective of pedagogy. Yamashita et al. proposed a fuzzy model for human relationships based on sociometry analysis. Yamashita's method is generated a partition tree from survey question results and to analyze human relationships based on the partition tree. When sociometry analysis is carried out, there is the disadvantage that it depends on the analyst. As preconditions for analysis, the nodes belonging to the same similarity in the partition tree have already been analyzed. In previous studies, the relationships among the groups belonging to different similarity levels was not specified. Therefore, we have newly developed an analytical method to solve the problem based on Yamashita's research. In order to evaluate these new analysis indices and fuzzy decision method, we used one example of data and its results. As a result of verification, we were able to obtain results equivalent to those done by experts and confirmed the usefulness of this new method. [ABSTRACT FROM AUTHOR]

Published
2019
Full Text
View/download PDF

12. Quicksort and Large Deviations

Author

McDiarmid, Colin, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kučera, Antonín, editor, Henzinger, Thomas A., editor, Nešetřil, Jaroslav, editor, Vojnar, Tomáš, editor, and Antoš, David, editor

Published
2013
Full Text
View/download PDF

13. Designing Scalable Parallel SAT Solvers

Author

Hyvärinen, Antti E. J., Manthey, Norbert, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Cimatti, Alessandro, editor, and Sebastiani, Roberto, editor

Published
2012
Full Text
View/download PDF

15. Grid-Based SAT Solving with Iterative Partitioning and Clause Learning

Author

Hyvärinen, Antti E. J., Junttila, Tommi, Niemelä, Ilkka, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Lee, Jimmy, editor

Published
2011
Full Text
View/download PDF

16. On Rectilinear Partitions with Minimum Stabbing Number

Author

de Berg, Mark, Khosravi, Amirali, Verdonschot, Sander, van der Weele, Vincent, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dehne, Frank, editor, Iacono, John, editor, and Sack, Jörg-Rüdiger, editor

Published
2011
Full Text
View/download PDF

17. Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures

Author

Chen, Danny Z., Wang, Haitao, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Iliopoulos, Costas S., editor, and Smyth, William F., editor

Published
2011
Full Text
View/download PDF

18. Partitioning SAT Instances for Distributed Solving

Author

Hyvärinen, Antti E. J., Junttila, Tommi, Niemelä, Ilkka, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Fermüller, Christian G., editor, and Voronkov, Andrei, editor

Published
2010
Full Text
View/download PDF

19. A simpler and more realistic subjective decision theory.

Author

Gaifman, Haim and Liu, Yang

Subjects
PROBABILITY theory, BOOLEAN algebra, AXIOMS, DECISION theory, STATISTICS
Abstract

In his classic book “the Foundations of Statistics” Savage develops a formal system of rational decision making. It is based on (i) a set of possible states of the world, (ii) a set of consequences, (iii) a set of acts, which are functions from states to consequences, and (iv) a preference relation over the acts, which represents the preferences of an idealized rational agent. The goal and the culmination of the enterprise is a representation theorem: any preference relation that satisfies certain arguably acceptable postulates determines a (finitely additive) probability distribution over the states and a utility assignment to the consequences, such that the preferences among acts are determined by their expected utilities. Additional problematic assumptions are however required in Savage’s proofs. First, there is a Boolean algebra of events (sets of states) which determines the richness of the set of acts. The probabilities are assigned to members of this algebra. Savage’s proof requires that this be a σ-algebra (i.e., closed under infinite countable unions and intersections), which makes for an extremely rich preference relation. On Savage’s view we should not require subjective probabilities to be σ-additive. He therefore finds the insistence on a σ-algebra peculiar and is unhappy with it. But he sees no way of avoiding it. Second, the assignment of utilities requires the constant act assumption: for every consequence there is a constant act, which produces that consequence in every state. This assumption is known to be highly counterintuitive. The present work contains two mathematical results. The first, and the more difficult one, shows that the σ-algebra assumption can be dropped. The second states that, as long as utilities are assigned to finite gambles only, the constant act assumption can be replaced by the more plausible and much weaker assumption that there are at least two non-equivalent constant acts. The second result also employs a novel way of deriving utilities in Savage-style systems—without appealing to von Neumann-Morgenstern lotteries. The paper discusses the notion of “idealized agent” that underlies Savage’s approach, and argues that the simplified system, which is adequate for all the actual purposes for which the system is designed, involves a more realistic notion of an idealized agent. [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

20. Free Skew Boolean Intersection Algebras and Set Partitions.

Author

Kudryavtseva, Ganna

Abstract

We show that atoms of the n-generated free left-handed skew Boolean intersection algebra are in a bijective correspondence with pointed partitions of non-empty subsets of {1, 2, . . . , n}. Furthermore, under the canonical inclusion into the k-generated free algebra, where k ≥ n, an atom of the n-generated free algebra decomposes into an orthogonal join of atoms of the k-generated free algebra in an agreement with the containment order on the respective partitions. As a consequence of these results, we describe the structure of finite free left-handed skew Boolean intersection algebras and express several their combinatorial characteristics in terms of Bell numbers and Stirling numbers of the second kind. We also look at the infinite case. For countably many generators, our constructions lead to the 'partition analogue' of the Cantor tree whose boundary is the 'partition variant' of the Cantor set. [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

23. phyBWT: Alignment-Free Phylogeny via eBWT Positional Clustering

Author

Veronica Guerrini and Alessio Conte and Roberto Grossi and Gianni Liti and Giovanna Rosone and Lorenzo Tattini, Guerrini, Veronica, Conte, Alessio, Grossi, Roberto, Liti, Gianni, Rosone, Giovanna, Tattini, Lorenzo, Veronica Guerrini and Alessio Conte and Roberto Grossi and Gianni Liti and Giovanna Rosone and Lorenzo Tattini, Guerrini, Veronica, Conte, Alessio, Grossi, Roberto, Liti, Gianni, Rosone, Giovanna, and Tattini, Lorenzo

Abstract

Molecular phylogenetics is a fundamental branch of biology. It studies the evolutionary relationships among the individuals of a population through their biological sequences, and may provide insights about the origin and the evolution of viral diseases, or highlight complex evolutionary trajectories. In this paper we develop a method called phyBWT, describing how to use the extended Burrows-Wheeler Transform (eBWT) for a collection of DNA sequences to directly reconstruct phylogeny, bypassing the alignment against a reference genome or de novo assembly. Our phyBWT hinges on the combinatorial properties of the eBWT positional clustering framework. We employ eBWT to detect relevant blocks of the longest shared substrings of varying length (unlike the k-mer-based approaches that need to fix the length k a priori), and build a suitable decomposition leading to a phylogenetic tree, step by step. As a result, phyBWT is a new alignment-, assembly-, and reference-free method that builds a partition tree without relying on the pairwise comparison of sequences, thus avoiding to use a distance matrix to infer phylogeny. The preliminary experimental results on sequencing data show that our method can handle datasets of different types (short reads, contigs, or entire genomes), producing trees of quality comparable to that found in the benchmark phylogeny.

Published
2022
Full Text
View/download PDF

24. Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations

Author

Bae, Sang Won, Lee, Chunseok, Ahn, Hee-Kap, Choi, Sunghee, Chwa, Kyung-Yong, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Tokuyama, Takeshi, editor

Published
2007
Full Text
View/download PDF

26. The Fuzzy Clustering Algorithm Based on AFS Topology

Author

Ding, Rui, Liu, Xiaodong, Chen, Yan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Wang, Lipo, editor, Jiao, Licheng, editor, Shi, Guanming, editor, Li, Xue, editor, and Liu, Jing, editor

Published
2006
Full Text
View/download PDF

27. On Interpretation of Non-atomic Values and Induction of Decision Rules in Fuzzy Relational Databases

Author

Angryk, Rafal A., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Rutkowski, Leszek, editor, Tadeusiewicz, Ryszard, editor, Zadeh, Lotfi A., editor, and Żurada, Jacek M., editor

Published
2006
Full Text
View/download PDF

28. Polyline Fitting of Planar Points Under Min-sum Criteria

Author

Aronov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fleischer, Rudolf, editor, and Trippen, Gerhard, editor

Published
2005
Full Text
View/download PDF

29. Generation of Sentence Parse Trees Using Parts of Speech

Author

Güngör, Tunga, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Biundo, Susanne, editor, Frühwirth, Thom, editor, and Palm, Günther, editor

Published
2004
Full Text
View/download PDF

30. Approximate Unions of Lines and Minkowski Sums

Author

van Kreveld, Marc, van der Stappen, A. Frank, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Albers, Susanne, editor, and Radzik, Tomasz, editor

Published
2004
Full Text
View/download PDF

35. Simulation Revisited

Author

Tan, Li, Cleaveland, Rance, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Margaria, Tiziana, editor, and Yi, Wang, editor

Published
2001
Full Text
View/download PDF

37. phyBWT: Alignment-Free Phylogeny via eBWT Positional Clustering

Author

Guerrini, Veronica, Conte, Alessio, Grossi, Roberto, Liti, Gianni, Rosone, Giovanna, Tattini, Lorenzo, University of Pisa - Università di Pisa, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and CNRS UMR 7284, Inserm U 1081, Université Côte d'Azur

Subjects
positional cluster, BWT, Bioinformatics, [SDV]Life Sciences [q-bio], partition tree, assembly-free, [INFO]Computer Science [cs], Mathematics of computing → Combinatorial algorithms, alignment-free, reference-free, referencefree, Phylogeny, Applied computing → Bioinformatics
Abstract

Molecular phylogenetics is a fundamental branch of biology. It studies the evolutionary relationships among the individuals of a population through their biological sequences, and may provide insights about the origin and the evolution of viral diseases, or highlight complex evolutionary trajectories. In this paper we develop a method called phyBWT, describing how to use the extended Burrows-Wheeler Transform (eBWT) for a collection of DNA sequences to directly reconstruct phylogeny, bypassing the alignment against a reference genome or de novo assembly. Our phyBWT hinges on the combinatorial properties of the eBWT positional clustering framework. We employ eBWT to detect relevant blocks of the longest shared substrings of varying length (unlike the k-mer-based approaches that need to fix the length k a priori), and build a suitable decomposition leading to a phylogenetic tree, step by step. As a result, phyBWT is a new alignment-, assembly-, and reference-free method that builds a partition tree without relying on the pairwise comparison of sequences, thus avoiding to use a distance matrix to infer phylogeny. The preliminary experimental results on sequencing data show that our method can handle datasets of different types (short reads, contigs, or entire genomes), producing trees of quality comparable to that found in the benchmark phylogeny., LIPIcs, Vol. 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022), pages 23:1-23:19

Published
2022
Full Text
View/download PDF

38. Fast floorplanning for FPGAs

Author

Emmert, John M., Randhar, Akash, Bhatia, Dinesh, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Hartenstein, Reiner W., editor, and Keevallik, Andres, editor

Published
1998
Full Text
View/download PDF

41. On set equality-testing

Author

Lam, Tak Wah, Lee, Ka Hing, Goos, G., editor, Hartmanis, J., editor, Bonuccelli, M., editor, Crescenzi, P., editor, and Petreschi, R., editor

Published
1994
Full Text
View/download PDF

47. Partitioned conditional generalized linear models for categorical responses.

Author

Peyhardi, Jean, Trottier, Catherine, and Guédon, Yann

Subjects
*LINEAR statistical models, *DATA analysis, *CATEGORIES (Mathematics), *REGRESSION analysis, *ORGANIZATIONAL structure
Abstract

In categorical data analysis, several regression models have been proposed for hierarchically structured responses, such as the nested logit model, the two-step model or the partitioned conditional model for partially ordered set. The specifications of these models are heterogeneous and they have been formally defined for only two or three levels in the hierarchy. Here, we introduce the class of partitioned conditional generalized linear models (PCGLMs) that encompasses all these models and is defined for any number of levels in the hierarchy. The hierarchical structure of these models is fully specified by a partition tree of categories. Using the genericity of the recently introduced (r,F,Z) specification of generalized linear models (GLMs) for categorical responses, it is possible to use different link functions and explanatory variables for each partitioning step. PCGLMs thus constitute a very flexible framework for modelling hierarchically structured categorical responses including partially ordered responses. [ABSTRACT FROM AUTHOR]

Published
2016
Full Text
View/download PDF

49. Dynamic partition trees

Author

Schipper, Haijo, Overmars, Mark H., Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Gilbert, John R., editor, and Karlsson, Rolf, editor

Published
1990
Full Text
View/download PDF

50. Tree-based space partition and merging ensemble learning framework for imbalanced problems

Author

Wenli Du, Zonghai Zhu, Dongdong Li, and Zhe Wang

Subjects
Information Systems and Management, Theoretical computer science, Computer science, 05 social sciences, 050301 education, 02 engineering and technology, Partition tree, Partition (database), Ensemble learning, Computer Science Applications, Theoretical Computer Science, Support vector machine, Regular distribution, Hyperplane, Artificial Intelligence, Control and Systems Engineering, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Tree based, 0503 education, Software
Abstract

Dealing with imbalanced problems is a significant challenge in machine learning, especially when the data set exhibits an irregular distribution. To this end, this paper proposes a tree-based space partition and merging ensemble learning framework known as the space partition tree (SPT), to partition the data space into two sub-spaces recursively. The partition hyperplane partitions the current space according to the maximum scatter direction of the majority set in the current space. When the partitioned sub-space satisfies the termination conditions, the sub-space is regarded as a decision space, and the decision region of the minority and majority classes is learned in this decision space. By merging the decision regions in all decision spaces, the SPT provides the entire decision region for the original problem. Thereby, the original complex problem can be divided into smaller problems with a relatively balanced and regular distribution. Moreover, the designed partition strategy offers advantages for the recognition of minority samples in the decision space. Finally, the space partition and merging exhibit superior geometric intuition and property of diversity. By introducing the biased penalties Support Vector Machine (BPSVM) into the SPT, the SPT-BPSVM demonstrates satisfactory performance and validates the effectiveness of the SPT in the experiment.

Published
2019
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results