# UHCL Faculty Works (Abstracts Only)

Permanent URI for this communityhttps://hdl.handle.net/10657.1/879

## Browse

# Browsing UHCL Faculty Works (Abstracts Only) by Author "Bettayeb, Said"

Now showing 1 - 14 of 14

- Results Per Page
- Sort Options

Item An Algorithm for Combining Graphs Based on Shared Knowledge(International Conference on Bioinformatics and Computational Biology, 2012) Bettayeb, SaidWe propose an algorithm for connecting nodes from multiple disconnected graphs based on a given tuple set representing shared knowledge. The set of tuples is used to create bridgeedges for combining two graphs. The path from a node in a graph to a node in the other graph passes through a bridgeedge. This method of combining two graphs will enable more comprehensive understanding and exploring of the relatedness of the knowledge entities (the nodes) in two graphs based on a given domain knowledge represented in the set of tuples. This approach has useful applications in various domains and in particular in bioinformatics. In bioinformatics, for example, we can explore the functional relationship between two gene products given their Gene Ontology annotation terms from the molecular function MF and biological process BP graphs of GO. Moreover, the proposed algorithm can be applied to WordNet to enable exploring the relative degree of relatedness of words from multiple lexical hierarchies, like nouns and verbs, within the WordNet.Item Computing Gene Functional Similarity Using Combined Graphs(Symposium on Applied Computing, 2012) Bettayeb, SaidThe Gene Ontology has been used extensively for measuring the functional similarity among genes of various organisms. All the existing gene similarity methods use either molecular function or biological process taxonomies in computing gene similarity. In this paper, we apply an algorithm for combining graphs to connect the molecular function (F) and biological process (P) taxonomies into one FP taxonomy graph. We then measure the functional similarity of two genes using the resulting FP graph with path length function. The two aspects of GO, molecular function and biological process, are combined by connecting F nodes with P nodes using gene ontology annotation, GOA, databases. By combining two GO graphs, we can have more comprehensive way to explore the functional relationships between genes. We conducted the evaluation on a dataset of OMIM disease phenotypes to estimate the similarity of disease proteins from various diseases.Item Embedding Rings into Faulty Twisted Hypercube(Journal of Computers and Artificial Intelligence, 1997) Bettayeb, SaidFault tolerance in hypercubes is achieved by exploiting inherent redundancy and executing tasks on faulty hypercubes. The authors consider tasks that require linear chain, ring, mesh, and torus structure, which are quite useful in parallel and pipeline computations. They assume the number of faults is on the order of the number of dimensions of the hypercube. The techniques are based on a key concept called free dimension, which can be used to partition a cube into subcubes such that each subcube contains, at most, one faulty node. Subgraphs are embedded in each subcube and then merged to form the entire graphItem Embedding Star Networks into Hypercubes(IEEE Transactions on Computers, 1996) Bettayeb, SaidThe star interconnection network has recently been suggested as an alternative to the hypercube. As hypercubes are often viewed as universal and capable of simulating other architectures efficiently, we investigate embeddings of star network into hypercubes. Our embeddings exhibit a marked trade off between dilation and expansion. For the n dimensional star network we exhibit: (1) a dilation N-1 embedding of S/sub n/ into H/sub n/, where N=[log/sub 2/(n!)]; (2) a dilation 2(d+1) embedding of S/sub n/ into H/sub 2d+n-1/ where d=[log/sub 2/([n/2]!)]; (3) a dilation 2d+2i embedding of S(2/sup i/m) into H(2/sup i/d+i2/sup i/m-2i+1) where d=[log/sub 2/(m!)]; (4) a dilation L embedding of S/sub n/ into H/sub d/, where L=1+[log/sub 2/(n!)], and d=(n-1)L; (5) a dilation (k+1)(k+2)/2 embedding of S/sub n/ into H(n(k+1)-2/sup k+1/+1) where k=[log/sub 2/(n-1)]; (6) a dilation 3 embedding of S/sub 2k+1/ into H(2k/sup 2/+k); and (7) a dilation 4 embedding of S/sub 3k+2/ into H(3k/sup 2/+3k+1). Some of the embeddings are in fact optimum, in both dilation and expansion for small values of n. We also show that the embedding of S/sub n/ into its optimum hypercube requires dilation /spl Omega/(log/sub 2/ n).Item The Genus of Complete Multipartite Graphs and Complete Multi- Layered Graphs(ACS/IEEE International Conference on Computer Systems and Applications, 2010) Bettayeb, SaidThe complete multipartite graph and the complete multi-layered graph are both generalizations of the complete bipartite graph. These two kinds of graphs have recursive structure and offer a very flexible choice of network size with respect to a fixed network order. This paper addresses the genus of the complete multipartite graph and the complete multi-layered graph which measures how efficiently we can set up a computer network using these graph layoutsItem Multiply-Twisted Hypercube with Five or More Dimensions is not Vertex Transitive(Information Processing Letters, 1995) Bettayeb, SaidItem On the Genus of Pancake Network(The International Journal of Information Technology, 2011) Bettayeb, SaidBoth the pancake graph and star graph are Cayley graphs and are especially attractive for parallel processing. They both have sublogarithmic diameter, and are fairly sparse compared to hypercubes. In this paper, we focus on another important property, namely the genus. The genus of a graph is the minimum number of handles needed for drawing the graph on the plane without edges crossing. We will investigate the upper bound and lower bound for the genus of pancake graph and compare these values with the genus of the star graph as well as that of the hypercube.Item On the Vertex-Disjoint Paths on Cayley Color Graphs(Journal of Computers and Artificial Intelligence, 1997) Bettayeb, SaidIn this paper, we study the strong connectivity of Cayley color graphs when a certain number of vertices are removed. We prove that there are 1/2D1/2 vertex-disjoint paths from every vertex to every other vertex in a Cayley color graph associated with a finite group G and a non redundant generating set D for G. We also extend this result to a certain class of Cayley graphs.Item Ontology Based Semantic Siimilarity for Protein Interactions(International Conference on Bioinformation and Computational Biology, 2013) Bettayeb, SaidOntology structure-based measures, like path length, have been used successfully for semantic similarity in various application domains. In bioinformatics, path length was used with the Gene Ontology (GO), using annotation terms, for gene similarity and clustering. In this paper, we propose to use the path length using GO annotations of proteins as a measure of protein similarity for scoring protein-protein interactions (PPIs). Proteins that interact with each other tend to have similar functions and be involved in similar biological processes compared to proteins that have no interactions. So, with the existence of a reliable well-established ontology, like GO, semantic similarity measures should be able to distinguish between, and rank, fairly well, the interacting and non-interacting protein pairs. The proposed method has been evaluated using datasets of positive and negative protein interactions from human and yeast proteomes. The evaluation results show that this method fares well when used to estimate similarity of interacting and non-interacting proteins.Item An Optimal Algorithm for Layered Wheel Floorplan Designs(Journal Networks, 1999) Bettayeb, SaidIn this paper, we present an efficient algorithm to solve the orientation optimization problem for a layered wheel floorplan. The strategy used is to generate all the nonredundant implementations for the floorplan. The computational complexities of the algorithm depend on the actual dimensions of the cells in the floorplan. In the best case, it takes O(n) time and O(n) space, where n is the number of layers in the floorplan. In the worst case, it takes O(2) time and O(2) space. Furthermore, we prove that the time and space complexities for the worst case are optimal. A set of conditions is obtained to check whether the floorplan belongs to the worst case. Using these conditions, we show that even though the worst case is theoretically unavoidable it is not encountered in practical situations where the cell dimensions are bounded.Item Simulation of the Crossed Cubes by the Shuffle Exchange Network(IEEE International Joint Conference on Computer, Information Systems Sciences and Engineering, 2011) Bettayeb, SaidThe structure of the interconnection network can be the deciding and limiting factor in performance and cost of parallel computers. Hypercube is one of the most popular interconnection networks. The symmetry, logarithmic diameter, regularity, fault-tolerance, high connectivity, simple routing, and reconfigurability of the hypercube make it a very attractive network for parallel computers. Extensive research has been done to study and improve its properties. Many interconnection networks like crossed cube, cube connected cycles, shuffle exchange graph etc. were proposed to improve one or more properties of hypercube. For example crossed cube, proposed to improve on the diameter of the hypercube and the diameter of the crossed cube is approximately half that of the hypercube [special characters omitted]. The hypercube and crossed cube both possesses a major drawback which is their variable degree i.e., degree of the node increases as the network grows in size. As an alternative to the hypercube, the shuffle exchange network is recently receiving much attention. The shuffle exchange network not only provides a logarithmic diameter, fault-tolerance, and simple routing but it also possess a constant node degree '3' which is independent of the network size. The shuffle-exchange graph is a Cayley graph and is especially attractive for parallel processing. The attractive properties of the crossed cube and the shuffle exchange graph have drawn my attention towards this thesis. In this thesis, we investigate the genus of the shuffle exchange graph and prove that the crossed cube of dimension 'n' can be simulated by the shuffle exchange graph with dilation '4'. In order to achieve constant dilation, we only consider normal algorithms.Item Stack and Queue Layouts for Toruses and Extended Hypercubes(Hawaii International Conference on System Sciences, 2010) Bettayeb, SaidLinear layouts play an important role in many applications including networks and VLSI design. Stack and queue layouts are two important types of linear layouts. We consider the stack number, s(G), and queue number, q(G), for multidimensional k-ary hypercubes and toruses. Heath, Leighton, and Rosenberg showed that d-dimensional ternary hypercubes have stack number ¿,(N 1/9 ), with N=3 d nodes. Malitz showed that E edges implies stack number O(¿E). For k-ary d-dimensional hypercubes, with N = k d vertices, Malitz's bound is O(k d/2 ). We improve this to 2 d+1 -3. The 2 d+1 -3 bound holds for arbitrary d-dimensional toruses. The queue number of d-dimensional k-ary hypercubes or toruses is bounded by O(d). Hence, Heath, Leighton, and Rosenberg exhibit an exponential tradeoff between s(G) and q(G) for multidimensional ternary hypercubes. Conversely, they conjectured that, for any G, q(G) is O(s(G)). We present a family {H} of modified multidimensional toruses and conjecture that q(H) is not O(s(H)).Item Trade-Off Considerations in Designing Efficient VLSI Feasible Interconnection Networks(VLSI Design, 1995) Bettayeb, SaidIt is well known that the hypercube has a rich set of good properties, and consequently it has been recognized an ideal structure for parallel computation. Nevertheless, according to the current VLSI technology, the implementation feasibility of the hypercube remains questionable when the size of the hypercube becomes large. Recent research efforts have been concentrated on finding good alternatives to the hypercube. The star graph was shown having many desirable properties of the hypercube, and in several aspects, the star graph is better than the hypercube. However, we observe that the star graph as a network has several disadvantages, compared with the hypercube. In this paper, we propose a class of new networks, the star-hypercube hybrid networks (or the SH networks). The SH network is a simple combination of both the star graph and the hypercube. This class of networks contains the star graph and the hypercube as subclasses. We show that the SH network is an efficient and versatile network for parallel computation, since it shares properties of both the hypercube and the star graph, and remedies several major disadvantages of the hypercube and the star graph. This class of networks provide more flexibility in choosing the size, degree, number of vertices, degree of fault tolerance, etc. in designing massively parallel computing structures feasible for VLSI implementations.Item Upper and Lower Bounds on the Pagenumber of the Book Embedding of the k-ary Hypercube(Journal of Digital Information Management, 2009) Bettayeb, SaidGraph embeddings play an important role in interconnection network and VLSI design. Determining the number of layers required to build a VLSI chip is just one of the many areas in which graph embeddings are used. A type of embedding that is helpful in determining the number of layers is a book embedding. We develop upper and lower bounds on the pagenumber of a book embedding of the k-ary hypercube along with an upper bound on the cumulative pagewidth.