Please use this identifier to cite or link to this item:
|Title:||Controlling size when aligning multiple genomic sequences with duplications|
|Citation:||Hou, M.,Berman, P.,Zhang, L.,Miller, W. (2006). Controlling size when aligning multiple genomic sequences with duplications. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4175 LNBI : 138-149. ScholarBank@NUS Repository.|
|Abstract:||For a genomic region containing a tandem gene cluster, a proper set of alignments needs to align only orthologous segments, i.e., those separated by a speciation event. Otherwise, methods for finding regions under evolutionary selection will not perform properly. Conversely, the alignments should indicate every orthologous pair of genes or genomic segments. Attaining this goal in practice requires a technique for avoiding a combinatorial explosion in the number of local alignments. To better understand this process, we model it as a graph problem of finding a minimum cardinality set of cliques that contain all edges. We provide an upper bound for an important class of graphs (the problem is 7 NP-hard and very difficult to approximate in the general case), and use the bound and computer simulations to evaluate two heuristic solutions. An implementation of one of them is evaluated on mammalian sequences from the α-globin gene cluster. © Springer-Verlag Berlin Heidelberg 2006.|
|Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Nov 9, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.