公开(公告)号：US08126235B2

公开(公告)日：2012-02-28

申请号：US12418933

申请日：2009-04-06

申请人： Xiaomeng Shi ,  Muriel Medard ,  Ralf Koetter ,  Nuala Ann Koetter, legal representative ,  Desmond S. Lun

发明人： Xiaomeng Shi ,  Muriel Medard ,  Ralf Koetter ,  Desmond S. Lun

IPC分类号： G06K9/00

CPC分类号： G06K9/0053 ,  G01N27/44717 ,  G01N30/8682 ,  G01N30/8696

摘要： In some aspects, a method of automated base-calling using at least one image obtained from a chemical sequencing process performed simultaneously on a plurality of DNA strands, the at least one image including intensity information corresponding to locations of at least one base in the plurality of DNA strands is provided. The method comprises processing the at least image to obtain a function corresponding to the intensity information in the at least one image for the at least one base, the function incorporating intensity information corresponding to each of the plurality of DNA strands, identifying a plurality of peaks in the function, the plurality of peaks indicating possible locations for the at least one base in the plurality of DNA strands, assigning membership to each of the plurality of peaks by determining whether each of the plurality of peaks is believed to have resulted from none, one or multiple of the plurality of DNA strands, and computing a sequence for the at least one base for each of the plurality of DNA strands based, at least in part, on the membership assignment.

摘要翻译： 在一些方面，一种使用从多个DNA链同时执行的化学测序过程获得的至少一个图像进行自动基本呼叫的方法，所述至少一个图像包括对应于多个基因中至少一个基因位置的强度信息 的DNA链。 所述方法包括处理所述至少一个图像以获得对应于所述至少一个基底的所述至少一个图像中的强度信息的函数，所述功能包括对应于所述多个DNA链中的每一个的强度信息，识别多个峰 在所述功能中，所述多个峰指示所述多个DNA链中所述至少一个碱基的可能位置，通过确定所述多个峰中的每一个是否被认为是由所述多个峰中的每一个赋予的， 至少部分地基于成员分配来计算多个DNA链中的一个或多个，以及针对所述多个DNA链中的每一个为所述至少一个碱基计算序列。

公开(公告)号：US20100074492A1

公开(公告)日：2010-03-25

申请号：US12418933

申请日：2009-04-06

申请人： Xiaomeng Shi ,  Muriel Medard ,  Ralf Koetter ,  Nuala Ann Koetter ,  Desmond S. Lun

发明人： Xiaomeng Shi ,  Muriel Medard ,  Ralf Koetter ,  Nuala Ann Koetter ,  Desmond S. Lun

IPC分类号： G06K9/00

CPC分类号： G06K9/0053 ,  G01N27/44717 ,  G01N30/8682 ,  G01N30/8696

摘要： In some aspects, a method of automated base-calling using at least one image obtained from a chemical sequencing process performed simultaneously on a plurality of DNA strands, the at least one image including intensity information corresponding to locations of at least one base in the plurality of DNA strands is provided. The method comprises processing the at least image to obtain a function corresponding to the intensity information in the at least one image for the at least one base, the function incorporating intensity information corresponding to each of the plurality of DNA strands, identifying a plurality of peaks in the function, the plurality of peaks indicating possible locations for the at least one base in the plurality of DNA strands, assigning membership to each of the plurality of peaks by determining whether each of the plurality of peaks is believed to have resulted from none, one or multiple of the plurality of DNA strands, and computing a sequence for the at least one base for each of the plurality of DNA strands based, at least in part, on the membership assignment.

摘要翻译： 在一些方面，一种使用从多个DNA链同时执行的化学测序过程获得的至少一个图像进行自动基本呼叫的方法，所述至少一个图像包括对应于多个基因中至少一个基因位置的强度信息 的DNA链。 所述方法包括处理所述至少一个图像以获得对应于所述至少一个基底的所述至少一个图像中的强度信息的函数，所述功能包括对应于所述多个DNA链中的每一个的强度信息，识别多个峰 在所述功能中，所述多个峰指示所述多个DNA链中所述至少一个碱基的可能位置，通过确定所述多个峰中的每一个是否被认为是由所述多个峰中的每一个赋予的， 至少部分地基于成员分配来计算多个DNA链中的一个或多个，以及针对所述多个DNA链中的每一个为所述至少一个碱基计算序列。

公开(公告)号：US07414978B2

公开(公告)日：2008-08-19

申请号：US11027889

申请日：2004-12-30

申请人： Desmond S. Lun ,  Muriel Medard ,  Tracey Ho ,  Ralf Koetter ,  Niranjan Ratnakar

发明人： Desmond S. Lun ,  Muriel Medard ,  Tracey Ho ,  Ralf Koetter ,  Niranjan Ratnakar

IPC分类号： H04B7/00

CPC分类号： H04L45/12 ,  H04L45/124

摘要： A method and computer program product for performing minimum cost routing with network coding is presented. The method and system model a network as a directed graph. A cost per unit flow is associated with each link of the directed graph. A link capacity is associated with each link of the directed graph. A network code is then computed that sets up a routing connection that achieves an optimal cost using the cost per unit flow for each link of the directed graph and using the link capacity for each link of the directed graph.

摘要翻译： 提出了一种通过网络编码实现最低成本路由的方法和计算机程序产品。 该方法和系统将网络建模为有向图。 单位流量的成本与有向图的每个链接相关联。 链接容量与有向图的每个链接相关联。 然后计算网络代码，其建立使用有向图的每个链路的每单位流的成本来实现最优成本的路由连接，并且使用有向图的每个链路的链路容量。

公开(公告)号：US08375102B2

公开(公告)日：2013-02-12

申请号：US13267764

申请日：2011-10-06

申请人： Muriel Medard ,  Supratim Deb ,  Ralf Koetter

发明人： Muriel Medard ,  Supratim Deb ,  Ralf Koetter

IPC分类号： G06F15/16

CPC分类号： H04L67/1095 ,  G06F17/30209 ,  H04L67/104

摘要： A method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is determined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.

公开(公告)号：US20050152391A1

公开(公告)日：2005-07-14

申请号：US10992463

申请日：2004-11-17

申请人： Michelle Effros ,  Tracey Ho ,  David Karger ,  Ralf Koetter ,  Muriel Medard

发明人： Michelle Effros ,  Tracey Ho ,  David Karger ,  Ralf Koetter ,  Muriel Medard

IPC分类号： H04L12/28 ,  H04L29/08

CPC分类号： H04L67/2823 ,  H04L67/2804 ,  H04L67/2814 ,  H04L67/288

摘要： A network and a method for transmitting processes in a network are disclosed, where a randomized coding approach is provided. Network nodes transmit on each outgoing link a linear combination of incoming signals, specified by independently and randomly chosen code coefficients from a finite field. The approach allows robust, distributed transmission and compression of information in networks and is advantageous over routing-based approaches.

摘要翻译： 公开了一种用于在网络中发送处理的网络和方法，其中提供随机编码方法。 网络节点在每个输出链路上传送来自有限域的独立随机选择的码系数指定的输入信号的线性组合。 该方法允许网络中的信息的鲁棒，分布式传输和压缩，并且对基于路由的方法是有利的。

公开(公告)号：US20120096124A1

公开(公告)日：2012-04-19

申请号：US13267764

申请日：2011-10-06

申请人： Muriel Medard ,  Supratim Deb ,  Ralf Koetter

发明人： Muriel Medard ,  Supratim Deb ,  Ralf Koetter

IPC分类号： G06F15/16

CPC分类号： H04L67/1095 ,  G06F17/30209 ,  H04L67/104

摘要： A method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is determined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.

摘要翻译： 提出了一种用于向分布式数据存储提供随机线性编码方法的方法和计算机程序产品。 文件被分成多个部分。 对于每个对等体（对等体意味着具有有限存储空间的存储位置），确定对等体可以存储的编码的数量。 每个编码片段通过采用整个文件的所有片段的随机线性组合来确定。 为每个编码块存储关联码矢量。 通过收集来自对等体的代码矢量和编码块并以收集的码矢量作为矩阵来检索文件。 当矩阵的维数等于文件的数量时，使用矩阵中的代码向量的集合来恢复文件。

公开(公告)号：US08046426B2

公开(公告)日：2011-10-25

申请号：US11026550

申请日：2004-12-30

申请人： Muriel Medard ,  Supratim Deb ,  Ralf Koetter

发明人： Muriel Medard ,  Supratim Deb ,  Ralf Koetter

IPC分类号： G06F15/16

CPC分类号： H04L67/1095 ,  G06F17/30209 ,  H04L67/104

摘要： A method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is determined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.

摘要翻译： 提出了一种用于向分布式数据存储提供随机线性编码方法的方法和计算机程序产品。 文件被分成多个部分。 对于每个对等体（对等体意味着具有有限存储空间的存储位置），确定对等体可以存储的编码的数量。 每个编码片段通过采用整个文件的所有片段的随机线性组合来确定。 为每个编码块存储关联码矢量。 通过收集来自对等体的代码矢量和编码块并以收集的码矢量作为矩阵来检索文件。 当矩阵的维数等于文件的数量时，使用矩阵中的代码向量的集合来恢复文件。

公开(公告)号：US20060146716A1

公开(公告)日：2006-07-06

申请号：US11027889

申请日：2004-12-30

申请人： Desmond Lun ,  Muriel Medard ,  Tracy Ho ,  Ralf Koetter ,  Niranjan Ratnakar

发明人： Desmond Lun ,  Muriel Medard ,  Tracy Ho ,  Ralf Koetter ,  Niranjan Ratnakar

IPC分类号： H04J3/14 ,  H04L12/28

CPC分类号： H04L45/12 ,  H04L45/124

摘要： A method and computer program product for performing minimum cost routing with network coding is presented. The method and system model a network as a directed graph. A cost per unit flow is associated with each link of the directed graph. A link capacity is associated with each link of the directed graph. A network code is then computed that sets up a routing connection that achieves an optimal cost using the cost per unit flow for each link of the directed graph and using the link capacity for each link of the directed graph.

摘要翻译： 提出了一种通过网络编码实现最低成本路由的方法和计算机程序产品。 该方法和系统将网络建模为有向图。 单位流量的成本与有向图的每个链接相关联。 链接容量与有向图的每个链接相关联。 然后计算网络代码，其建立使用有向图的每个链路的每单位流的成本来实现最优成本的路由连接，并且使用有向图的每个链路的链路容量。

公开(公告)号：US07706365B2

公开(公告)日：2010-04-27

申请号：US10992463

申请日：2004-11-17

申请人： Michelle Effros ,  Tracey Ho ,  David Karger ,  Ralf Koetter ,  Muriel Medard

发明人： Michelle Effros ,  Tracey Ho ,  David Karger ,  Ralf Koetter ,  Muriel Medard

IPC分类号： H04L12/56

CPC分类号： H04L67/2823 ,  H04L67/2804 ,  H04L67/2814 ,  H04L67/288

摘要： A network and a method for transmitting processes in a network are disclosed, where a randomized coding approach is provided. Network nodes transmit on each outgoing link a linear combination of incoming signals, specified by independently and randomly chosen code coefficients from a finite field. The approach allows robust, distributed transmission and compression of information in networks and is advantageous over routing-based approaches.

摘要翻译： 公开了一种用于在网络中发送处理的网络和方法，其中提供随机编码方法。 网络节点在每个输出链路上传送来自有限域的独立随机选择的码系数指定的输入信号的线性组合。 该方法允许网络中的信息的鲁棒，分布式传输和压缩，并且对基于路由的方法是有利的。

公开(公告)号：US20060149753A1

公开(公告)日：2006-07-06

申请号：US11026550

申请日：2004-12-30

申请人： Muriel Medard ,  Supratim Deb ,  Ralf Koetter

发明人： Muriel Medard ,  Supratim Deb ,  Ralf Koetter

IPC分类号： G06F17/30

CPC分类号： H04L67/1095 ,  G06F17/30209 ,  H04L67/104

摘要： A method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is detrmined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.

摘要翻译： 提出了一种用于向分布式数据存储提供随机线性编码方法的方法和计算机程序产品。 文件被分成多个部分。 对于每个对等体（对等体意味着具有有限存储空间的存储位置），确定对等体可以存储的编码的数量。 每个编码器通过采用整个文件的所有片段的随机线性组合来确定。 为每个编码块存储关联码矢量。 通过收集来自对等体的代码矢量和编码块并以收集的码矢量作为矩阵来检索文件。 当矩阵的维数等于文件的数量时，使用矩阵中的代码向量的集合来恢复文件。